A new perspective on low-rank optimization
From MaRDI portal
(Redirected from A new perspective on low-rank optimization)
Abstract: A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable convex relaxations. We invoke the matrix perspective function - the matrix analog of the perspective function - and characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix perspective function with orthogonal projection matrices-the matrix analog of binary variables which capture the row-space of a matrix-to develop a matrix perspective reformulation technique that reliably obtains strong relaxations for a variety of low-rank problems, including reduced rank regression, non-negative matrix factorization, and factor analysis. Moreover, we establish that these relaxations can be modeled via semidefinite constraints and thus optimized over tractably. The proposed approach parallels and generalizes the perspective reformulation technique in mixed-integer optimization and leads to new relaxations for a broad class of problems.
Recommendations
Cites work
- A branch-and-cut method for 0-1 mixed convex programming
- A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A mathematical view of interior-point methods in convex optimization
- A matrix convexity approach to some celebrated quantum inequalities
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- A unified approach to mixed-integer optimization problems with logical constraints
- An analysis of approximations for maximizing submodular set functions—I
- Approximating K‐means‐type Clustering via Semidefinite Programming
- Benders decomposition without separability: a computational study for capacitated facility location problems
- Best subset selection via a modern optimization lens
- Certifiably optimal low rank factor analysis
- Convex Analysis on the Hermitian Matrices
- Convex programming for disjunctive convex optimization
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Eigenvalue techniques for convex objective, nonconvex optimization problems
- Estimation of (near) low-rank matrices with noise and high-dimensional scaling
- Exact matrix completion via convex optimization
- Handbook of semidefinite programming. Theory, algorithms, and applications
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 7625166 (Why is no real title available?)
- Ideal formulations for constrained convex optimization problems with indicator variables
- Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- Linear Matrix Inequalities in System and Control Theory
- Matrix Analysis
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Nearly unbiased variable selection under minimax concave penalty
- Non-commutative perspectives
- Nonlinear programming
- On a functional operation generating convex functions. I: Duality
- On a functional operation generating convex functions. II: Algebraic properties
- On doubly positive semidefinite programming relaxations
- On the convexity of the multiplicative potential and penalty functions and related topics
- On the copositive representation of binary and continuous nonconvex quadratic programs
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- On the semidefinite representation of real functions applied to symmetric matrices
- On the Sum of the Largest Eigenvalues of a Symmetric Matrix
- On the tightness of SDP relaxations of QCQPs
- Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective functions: properties, constructions, and examples
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Perspectives of matrix convex functions
- Scalable algorithms for the sparse ridge regression
- Semidefinite approximations of the matrix logarithm
- Sensor Selection via Convex Optimization
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Sparse learning via Boolean relaxations
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Sparse regression: scalable algorithms and empirical performance
- Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
- Tensor Decompositions and Applications
- The Generalized Inverse of a Nonnegative Matrix
- The proper formula for relative entropy and its asymptotics in quantum probability
- The role of perspective functions in convexity, polyconvexity, rank-one convexity and separate convexity
- Trace inequalities and quantum entropy: an introductory course
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
- Various averaging operations onto subalgebras
Cited in
(5)- Optimization challenges in the structured low rank approximation problem
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Constrained optimization of rank-one functions with indicator variables
- On the partial convexification for low-rank spectral optimization: rank bounds and algorithms
- A parametric approach for solving convex quadratic optimization with indicators over trees
This page was built for publication: A new perspective on low-rank optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052053)
