The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform
Cédric Févotte - One of the best experts on this subject based on the ideXlab platform.
-
Positive Semidefinite Matrix Factorization Based on Truncated Wirtinger Flow
2021Co-Authors: Dana Lahat, Cédric FévotteAbstract:This paper deals with algorithms for Positive Semidefinite Matrix factorization (PSDMF). PSDMF is a recently-proposed extension of nonnegative Matrix factorization with applications in combinatorial optimization, among others. In this paper, we focus on improving the local convergence of an alternating block gradient (ABG) method for PSDMF in a noise-free setting by replacing the quadratic objective function with the Poisson log-likelihood. This idea is based on truncated Wirtinger flow (TWF), a phase retrieval (PR) method that trims outliers in the gradient and thus regularizes it. Our motivation is a recent result linking PR with PSDMF. Our numerical experiments validate that the numerical benefits of TWF may carry over to PSDMF despite the more challenging setting, when initialized within its region of convergence. We then extend TWF from PR to affine rank minimization (ARM), and show that although the outliers are no longer an issue in the ARM setting, PSDMF with the new objective function may still achieves a smaller error for the same number of iterations. In a broader view, our results indicate that a proper choice of objective function may enhance convergence of Matrix (or tensor) factorization methods.
-
Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization.
arXiv: Signal Processing, 2020Co-Authors: Dana Lahat, Yanbin Lang, Vincent Y. F. Tan, Cédric FévotteAbstract:Positive Semidefinite Matrix factorization (PSDMF) expresses each entry of a nonnegative Matrix as the inner product of two Positive Semidefinite (psd) matrices. When all these psd matrices are constrained to be diagonal, this model is equivalent to nonnegative Matrix factorization. Applications include combinatorial optimization, quantum-based statistical models, and recommender systems, among others. However, despite the increasing interest in PSDMF, only a few PSDMF algorithms were proposed in the literature. In this paper, we show that PSDMF algorithms can be designed based on phase retrieval (PR) and affine rank minimization (ARM) algorithms. This procedure allows a significant shortcut in designing new PSDMF algorithms, as it allows to leverage some of the useful numerical properties of existing PR and ARM methods to the PSDMF framework. Motivated by this idea, we introduce a new family of PSDMF algorithms based on singular value projection (SVP) and iterative hard thresholding (IHT). This family subsumes previously-proposed projected gradient PSDMF methods; additionally, we show a new connection between SVP-based methods and majorization-minimization. Numerical experiments show that our proposed methods outperform state-of-the-art coordinate descent algorithms in terms of convergence speed and computational complexity, in certain scenarios. In certain cases, our proposed normalized-IHT-based method is the only algorithm able to find a solution. These results support our claim that the PSDMF framework can inherit desired numerical properties from PR and ARM algorithms, leading to more efficient PSDMF algorithms, and motivate further study of the links between these models.
-
Positive Semidefinite Matrix FACTORIZATION: A LINK TO PHASE RETRIEVAL AND A BLOCK GRADIENT ALGORITHM
2020Co-Authors: Dana Lahat, Cédric FévotteAbstract:This paper deals with Positive Semidefinite Matrix factorization (PSDMF). PSDMF writes each entry of a nonnegative Matrix as the inner product of two symmetric Positive Semidefinite matrices. PSDMF generalizes nonnegative Matrix factorization. Exact PSDMF has found applications in combinatorial optimization, quantum communication complexity, and quantum information theory, among others. In this paper, we show, for the first time, a link between PSDMF and the problem of Matrix recovery from phaseless measurements, which includes phase retrieval. We demonstrate the usefulness of this observation by proposing a new type of local optimization scheme for PSDMF, which is based on a generalization of the Wirtinger flow method for phase retrieval. Numerical experiments show that our algorithm can performs as well as state-of-the-art algorithms, in certain setups. We suggest that this link between the two types of problems, which have until now been addressed separately, opens the door to new applications, algorithms, and insights.
-
ICASSP - Positive Semidefinite Matrix Factorization: A Link to Phase Retrieval And A Block Gradient Algorithm
ICASSP 2020 - 2020 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2020Co-Authors: Dana Lahat, Cédric FévotteAbstract:This paper deals with Positive Semidefinite Matrix factorization (PS-DMF). PSDMF writes each entry of a nonnegative Matrix as the inner product of two symmetric Positive Semidefinite matrices. PS-DMF generalizes nonnegative Matrix factorization. Exact PSDMF has found applications in combinatorial optimization, quantum communication complexity, and quantum information theory, among others. In this paper, we show, for the first time, a link between PS-DMF and the problem of Matrix recovery from phaseless measurements, which includes phase retrieval. We demonstrate the usefulness of this observation by proposing a new type of local optimization scheme for PSDMF, which is based on a generalization of the Wirtinger flow method for phase retrieval. Numerical experiments show that our algorithm can performs as well as state-of-the-art algorithms, in certain setups. We suggest that this link between the two types of problems, which have until now been addressed separately, opens the door to new applications, algorithms, and insights.
Dana Lahat - One of the best experts on this subject based on the ideXlab platform.
-
Positive Semidefinite Matrix Factorization Based on Truncated Wirtinger Flow
2021Co-Authors: Dana Lahat, Cédric FévotteAbstract:This paper deals with algorithms for Positive Semidefinite Matrix factorization (PSDMF). PSDMF is a recently-proposed extension of nonnegative Matrix factorization with applications in combinatorial optimization, among others. In this paper, we focus on improving the local convergence of an alternating block gradient (ABG) method for PSDMF in a noise-free setting by replacing the quadratic objective function with the Poisson log-likelihood. This idea is based on truncated Wirtinger flow (TWF), a phase retrieval (PR) method that trims outliers in the gradient and thus regularizes it. Our motivation is a recent result linking PR with PSDMF. Our numerical experiments validate that the numerical benefits of TWF may carry over to PSDMF despite the more challenging setting, when initialized within its region of convergence. We then extend TWF from PR to affine rank minimization (ARM), and show that although the outliers are no longer an issue in the ARM setting, PSDMF with the new objective function may still achieves a smaller error for the same number of iterations. In a broader view, our results indicate that a proper choice of objective function may enhance convergence of Matrix (or tensor) factorization methods.
-
Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization.
arXiv: Signal Processing, 2020Co-Authors: Dana Lahat, Yanbin Lang, Vincent Y. F. Tan, Cédric FévotteAbstract:Positive Semidefinite Matrix factorization (PSDMF) expresses each entry of a nonnegative Matrix as the inner product of two Positive Semidefinite (psd) matrices. When all these psd matrices are constrained to be diagonal, this model is equivalent to nonnegative Matrix factorization. Applications include combinatorial optimization, quantum-based statistical models, and recommender systems, among others. However, despite the increasing interest in PSDMF, only a few PSDMF algorithms were proposed in the literature. In this paper, we show that PSDMF algorithms can be designed based on phase retrieval (PR) and affine rank minimization (ARM) algorithms. This procedure allows a significant shortcut in designing new PSDMF algorithms, as it allows to leverage some of the useful numerical properties of existing PR and ARM methods to the PSDMF framework. Motivated by this idea, we introduce a new family of PSDMF algorithms based on singular value projection (SVP) and iterative hard thresholding (IHT). This family subsumes previously-proposed projected gradient PSDMF methods; additionally, we show a new connection between SVP-based methods and majorization-minimization. Numerical experiments show that our proposed methods outperform state-of-the-art coordinate descent algorithms in terms of convergence speed and computational complexity, in certain scenarios. In certain cases, our proposed normalized-IHT-based method is the only algorithm able to find a solution. These results support our claim that the PSDMF framework can inherit desired numerical properties from PR and ARM algorithms, leading to more efficient PSDMF algorithms, and motivate further study of the links between these models.
-
Positive Semidefinite Matrix FACTORIZATION: A LINK TO PHASE RETRIEVAL AND A BLOCK GRADIENT ALGORITHM
2020Co-Authors: Dana Lahat, Cédric FévotteAbstract:This paper deals with Positive Semidefinite Matrix factorization (PSDMF). PSDMF writes each entry of a nonnegative Matrix as the inner product of two symmetric Positive Semidefinite matrices. PSDMF generalizes nonnegative Matrix factorization. Exact PSDMF has found applications in combinatorial optimization, quantum communication complexity, and quantum information theory, among others. In this paper, we show, for the first time, a link between PSDMF and the problem of Matrix recovery from phaseless measurements, which includes phase retrieval. We demonstrate the usefulness of this observation by proposing a new type of local optimization scheme for PSDMF, which is based on a generalization of the Wirtinger flow method for phase retrieval. Numerical experiments show that our algorithm can performs as well as state-of-the-art algorithms, in certain setups. We suggest that this link between the two types of problems, which have until now been addressed separately, opens the door to new applications, algorithms, and insights.
-
ICASSP - Positive Semidefinite Matrix Factorization: A Link to Phase Retrieval And A Block Gradient Algorithm
ICASSP 2020 - 2020 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2020Co-Authors: Dana Lahat, Cédric FévotteAbstract:This paper deals with Positive Semidefinite Matrix factorization (PS-DMF). PSDMF writes each entry of a nonnegative Matrix as the inner product of two symmetric Positive Semidefinite matrices. PS-DMF generalizes nonnegative Matrix factorization. Exact PSDMF has found applications in combinatorial optimization, quantum communication complexity, and quantum information theory, among others. In this paper, we show, for the first time, a link between PS-DMF and the problem of Matrix recovery from phaseless measurements, which includes phase retrieval. We demonstrate the usefulness of this observation by proposing a new type of local optimization scheme for PSDMF, which is based on a generalization of the Wirtinger flow method for phase retrieval. Numerical experiments show that our algorithm can performs as well as state-of-the-art algorithms, in certain setups. We suggest that this link between the two types of problems, which have until now been addressed separately, opens the door to new applications, algorithms, and insights.
Ao Tang - One of the best experts on this subject based on the ideXlab platform.
-
A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
IEEE Transactions on Signal Processing, 2011Co-Authors: Meng Wang, Weiyu Xu, Ao TangAbstract:This paper investigates the uniqueness of a nonnegative vector solution and the uniqueness of a Positive Semidefinite Matrix solution to underdetermined linear systems. A vector solution is the unique solution to an underdetermined linear system only if the measurement Matrix has a row-span intersecting the Positive orthant. Focusing on two types of binary measurement matrices, Bernoulli 0-1 matrices and adjacency matrices of general expander graphs, we show that, in both cases, the support size of a unique nonnegative solution can grow linearly, namely O(n), with the problem dimension n . We also provide closed-form characterizations of the ratio of this support size to the signal dimension. For the Matrix case, we show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique Positive Semidefinite Matrix solution to the compressed linear observations. We further show that a randomly generated Gaussian linear compressed observations operator will satisfy this condition with overwhelmingly high probability.
-
on the uniqueness of Positive Semidefinite Matrix solution under compressed observations
International Symposium on Information Theory, 2010Co-Authors: Ao TangAbstract:In this paper, we investigate the uniqueness of Positive Semidefinite Matrix solution to compressed linear observations. We show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique Positive Semidefinite Matrix solution to the compressed linear observations. It is further shown, through concentration of measure phenomenon and sphere covering arguments, that a randomly generated Gaussian linear compressed observations operator will satisfy this necessary and sufficient condition with overwhelmingly large probability.
-
ISIT - On the uniqueness of Positive Semidefinite Matrix solution under compressed observations
2010 IEEE International Symposium on Information Theory, 2010Co-Authors: Ao TangAbstract:In this paper, we investigate the uniqueness of Positive Semidefinite Matrix solution to compressed linear observations. We show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique Positive Semidefinite Matrix solution to the compressed linear observations. It is further shown, through concentration of measure phenomenon and sphere covering arguments, that a randomly generated Gaussian linear compressed observations operator will satisfy this necessary and sufficient condition with overwhelmingly large probability.
Mehran Mesbahi - One of the best experts on this subject based on the ideXlab platform.
-
On the rank minimization problem
Proceedings of the 2004 American Control Conference, 2004Co-Authors: Yoonsoo Kim, Mehran MesbahiAbstract:After a brief overview of the problem of finding the extremal (minimum or maximum) rank Positive Semidefinite Matrix subject to Matrix inequalities, we identify a few new classes of such problems that can be efficiently solved. We then proceed to present an algorithm for solving the general class of rank minimization problems.
Antonios Varvitsiotis - One of the best experts on this subject based on the ideXlab platform.
-
Positive Semidefinite Matrix completion, universal rigidity and the Strong Arnold Property
Linear Algebra and its Applications, 2014Co-Authors: Monique Laurent, Antonios VarvitsiotisAbstract:This paper addresses the following three topics: Positive semidenite (psd) Matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidenite programming as unifying theme. Our main contribution is a sufcient condition for constructing partial psd matrices which admit a unique completion to a full psd Matrix. Such partial matrices are an essential tool in the study of the Gram dimension gd(G) of a graph G, a recently studied graph parameter related to the low psd Matrix completion problem. Additionally, we derive an elementary proof of Connelly’s sucient condition for universal rigidity of tensegrity frameworks and we investigate the links between these two sucient conditions. We also give a geometric characterization of psd matrices satisfying the Strong Arnold Property in terms of nondegeneracy of an associated semidenite program, which we use to establish some links between the Gram dimension gd( ) and the Colin de Verdi ere type graph parameter = ( ).
-
Complexity of the Positive Semidefinite Matrix completion problem with a rank constraint
Discrete Geometry and Optimization, 2013Co-Authors: Marianna Nagy, Monique Laurent, Antonios VarvitsiotisAbstract:We consider the decision problem asking whether a partial rational symmetric Matrix with an all-ones diagonal can be completed to a full Positive Semidefinite Matrix of rank at most k. We show that this problem is \(\mathcal{N}\mathcal{P}\)-hard for any fixed integer k ≥ 2. In other words, for k ≥ 2, it is \(\mathcal{N}\mathcal{P}\)-hard to test membership in the rank constrained elliptope \(\mathcal{E}_{k}(G)\), defined by the set of all partial matrices with an all-ones diagonal and off-diagonal entries specified at the edges of G, that can be completed to a Positive Semidefinite Matrix of rank at most k. Additionally, we show that deciding membership in the convex hull of \(\mathcal{E}_{k}(G)\) is also \(\mathcal{N}\mathcal{P}\)-hard for any fixed integer k ≥ 2.
-
A new graph parameter related to bounded rank Positive Semidefinite Matrix completions
Mathematical Programming, 2013Co-Authors: Monique Laurent, Antonios VarvitsiotisAbstract:htmlabstractThe Gram dimension gd(G) of a graph G is the smallest inte- ger k ≥ 1 such that any partial real symmetric Matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of G, can be completed to a Positive Semidefinite Matrix of rank at most k (assuming a Positive Semidefinite completion exists). For any fixed k the class of graphs satisfying gd(G) ≤ k is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is Kk+1 for k ≤ 3 and that there are two minimal forbidden minors: K5 and K2,2,2 for k = 4. We also show some close connections to Euclidean realizations of graphs and to the graph parameter ν=(G) of [21]. In particular, our characterization of the graphs with gd(G) ≤ 4 implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly [8,9] and of the graphs with ν=(G) ≤ 4 of van der Holst [21]
-
A new graph parameter related to bounded rank Positive Semidefinite Matrix completions
Mathematical Programming, 2013Co-Authors: Monique Laurent, Antonios VarvitsiotisAbstract:The Gram dimension $$\mathrm{gd}(G)$$ of a graph $$G$$ is the smallest integer $$k\ge 1$$ such that any partial real symmetric Matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $$G$$ , can be completed to a Positive Semidefinite Matrix of rank at most $$k$$ (assuming a Positive Semidefinite completion exists). For any fixed $$k$$ the class of graphs satisfying $$\mathrm{gd}(G) \le k$$ is minor closed, hence it can be characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $$K_{k+1}$$ for $$k\le 3$$ and that there are two minimal forbidden minors: $$K_5$$ and $$K_{2,2,2}$$ for $$k=4$$ . We also show some close connections to Euclidean realizations of graphs and to the graph parameter $$\nu ^=(G)$$ of van der Holst (Combinatorica 23(4):633---651, 2003). In particular, our characterization of the graphs with $$\mathrm{gd}(G)\le 4$$ implies the forbidden minor characterization of the 3-realizable graphs of Belk (Discret Comput Geom 37:139---162, 2007) and Belk and Connelly (Discret Comput Geom 37:125---137, 2007) and of the graphs with $$\nu ^=(G) \le 4$$ of van der Holst (Combinatorica 23(4):633---651, 2003).
-
A new graph parameter related to bounded rank Positive Semidefinite Matrix completions
arXiv: Optimization and Control, 2012Co-Authors: Monique Laurent, Antonios VarvitsiotisAbstract:The Gram dimension $\gd(G)$ of a graph $G$ is the smallest integer $k\ge 1$ such that any partial real symmetric Matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $G$, can be completed to a Positive Semidefinite Matrix of rank at most $k$ (assuming a Positive Semidefinite completion exists). For any fixed $k$ the class of graphs satisfying $\gd(G) \le k$ is minor closed, hence it can characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $K_{k+1}$ for $k\le 3$ and that there are two minimal forbidden minors: $K_5$ and $K_{2,2,2}$ for $k=4$. We also show some close connections to Euclidean realizations of graphs and to the graph parameter $\nu^=(G)$ of \cite{H03}. In particular, our characterization of the graphs with $\gd(G)\le 4$ implies the forbidden minor characterization of the 3-realizable graphs of Belk and Connelly \cite{Belk,BC} and of the graphs with $\nu^=(G) \le 4$ of van der Holst \cite{H03}.