An approximation theory of matrix rank minimization and its application to quadratic equations
From MaRDI portal
Publication:417562
DOI10.1016/J.LAA.2012.02.021zbMATH Open1242.65086arXiv1010.0851OpenAlexW2963942504MaRDI QIDQ417562FDOQ417562
Publication date: 14 May 2012
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: Matrix rank minimization problems are gaining a plenty of recent attention in both mathematical and engineering fields. This class of problems, arising in various and across-discipline applications, is known to be NP-hard in general. In this paper, we aim at providing an approximation theory for the rank minimization problem, and prove that a rank minimization problem can be approximated to any level of accuracy via continuous optimization (especially, linear and nonlinear semidefinite programming) problems. One of the main results in this paper shows that if the feasible set of the problem has a minimum rank element with the least F-norm (i.e., Frobenius norm), then the solution of the approximation problem converges to the minimum rank solution of the original problem as the approximation parameter tends to zero. The tractability under certain conditions and convex relaxation of the approximation problem are also discussed. The methodology and results in this paper provide a new theoretical basis for the development of some efficient computational methods for solving rank minimization problems. An immediate application of this theory to the system of quadratic equations is presented in this paper. It turns out that the condition for such a system without a nonzero solution can be characterized by a rank minimization problem, and thus the proposed approximation theory can be used to establish some sufficient conditions for the system to possess only zero solution.
Full work available at URL: https://arxiv.org/abs/1010.0851
Recommendations
- A new approximation of the matrix rank function and its application to matrix rank minimization
- Minimum rank solutions to the matrix approximation problems in the spectral norm
- Least squares solutions to the rank-constrained matrix approximation problem in the Frobenius norm
- Approximating minimum norm solutions of rank-deficient least squares problems
- scientific article
- A note on approximating quadratic programming with rank constraint
- scientific article
- Extremal ranks of a quadratic matrix expression with applications
- On critical points of quadratic low-rank matrix optimization problems
- A minimum norm approach for low-rank approximations of a matrix
Numerical mathematical programming methods (65K05) Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)
Cites Work
- Linear Matrix Inequalities in System and Control Theory
- Exact matrix completion via convex optimization
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Compressed sensing
- Nuclear norm minimization for the planted clique and biclique problems
- Fixed point and Bregman iterative methods for matrix rank minimization
- The geometry of graphs and some of its algorithmic applications
- Über das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen
- On the Field of Values of a Matrix
- Sparse Approximate Solutions to Linear Systems
- On the rank minimization problem over a positive semidefinite linear matrix inequality
- Convergence of fixed-point continuation algorithms for matrix rank minimization
- On linear combinations of quadratic forms
- A recurring theorem about pairs of quadratic forms and extensions: A survey
- Potpourri of Conjectures and Open Questions in Nonlinear Analysis and Optimization
- On the rank minimization problem and its control applications
- A new approach to collaborative filtering: operator estimation with spectral regularization
- Null space conditions and thresholds for rank minimization
- Rank-one LMI approach to simultaneous stabilization of linear systems.
- Theory of semidefinite programming for sensor network localization
- Distance matrix completion by numerical optimization
- Permanently going back and forth between the ``quadratic world and the ``convexity world in optimization
- Rank-one solutions for homogeneous linear matrix equations over the positive semidefinite cone
- A unified approach for minimizing composite norms
- Title not available (Why is that?)
Cited In (19)
- Miscellaneous reverse order laws for generalized inverses of matrix products with applications
- An efficient solution method for rank two quasiconcave minimization problems
- A new approximation of the matrix rank function and its application to matrix rank minimization
- On critical points of quadratic low-rank matrix optimization problems
- Minimum rank positive semidefinite solution to the matrix approximation problem in the spectral norm
- A reweighted nuclear norm minimization algorithm for low rank matrix recovery
- First order optimality conditions for mathematical programs with semidefinite cone complementarity constraints
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- The viscosity subdifferential of the rank function via the corresponding subdifferential of its Moreau envelopes
- Two relaxation methods for rank minimization problems
- Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications
- Rank structured approximation method for quasi-periodic elliptic problems
- A variational approach of the rank function
- Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers
- On finding a generalized lowest rank solution to a linear semi-definite feasibility problem
- A new nonconvex approach to low-rank matrix completion with application to image inpainting
- A low-rank solution method for Riccati equations with indefinite quadratic terms
- Approximation of rank function and its application to the nearest low-rank correlation matrix
- Rank-constrained optimization and its applications
Uses Software
This page was built for publication: An approximation theory of matrix rank minimization and its application to quadratic equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q417562)
