Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
From MaRDI portal
Abstract: The topic of recovery of a structured model given a small number of linear observations has been well-studied in recent years. Examples include recovering sparse or group-sparse vectors, low-rank matrices, and the sum of sparse and low-rank matrices, among others. In various applications in signal processing and machine learning, the model of interest is known to be structured in several ways at the same time, for example, a matrix that is simultaneously sparse and low-rank. Often norms that promote each individual structure are known, and allow for recovery using an order-wise optimal number of measurements (e.g., norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable to minimize a combination of such norms. We show that, surprisingly, if we use multi-objective optimization with these norms, then we can do no better, order-wise, than an algorithm that exploits only one of the present structures. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation, i.e. not one that is a function of the convex relaxations used for each structure. We then specialize our results to the case of sparse and low-rank matrices. We show that a nonconvex formulation of the problem can recover the model from very few measurements, which is on the order of the degrees of freedom of the matrix, whereas the convex problem obtained from a combination of the and nuclear norms requires many more measurements. This proves an order-wise gap between the performance of the convex and nonconvex recovery problems in this case. Our framework applies to arbitrary structure-inducing norms as well as to a wide range of measurement ensembles. This allows us to give performance bounds for problems such as sparse phase retrieval and low-rank tensor completion.
Cited in
(47)- Trace regression model with simultaneously low rank and row(column) sparse parameter
- Equivalent Lipschitz surrogates for zero-norm and rank optimization problems
- A geometric analysis of phase retrieval
- A convex variational model for learning convolutional image atoms from incomplete data
- Sparse power factorization: balancing peakiness and sample complexity
- Tensor theta norms and low rank recovery
- Proof methods for robust low-rank matrix recovery
- An optimal statistical and computational framework for generalized tensor estimation
- Constructing confidence intervals for the signals in sparse phase retrieval
- Enhanced image approximation using shifted rank-1 reconstruction
- Compressive total variation for image reconstruction and restoration
- Tensor completion based on triple tubal nuclear norm
- Solving equations of random convex functions via anchored regression
- Non-intrusive tensor reconstruction for high-dimensional random PDEs
- Optimization on the hierarchical Tucker manifold - applications to tensor completion
- Sparse and low-rank covariance matrix estimation
- Low-rank and joint-sparse signal recovery using sparse Bayesian learning in a WBAN
- Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
- Generic error bounds for the generalized Lasso with sub-exponential data
- Low complexity regularization of linear inverse problems
- Low-rank approximation and completion of positive tensors
- Sharp MSE bounds for proximal denoising
- Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation
- Self-calibration and biconvex compressive sensing
- Recovering structured signals in noise: least-squares meets compressed sensing
- Sparse model uncertainties in compressed sensing with application to convolutions and sporadic communication
- Near-optimal estimation of simultaneously sparse and low-rank matrices from nested linear measurements
- Flavors of compressive sensing
- Sparse Matrix Graphical Models
- Extreme point inequalities and geometry of the rank sparsity ball
- Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems
- An Unbiased Approach to Low Rank Recovery
- Jointly low-rank and bisparse recovery: questions and partial answers
- Subspace clustering by \((k,k)\)-sparse matrix factorization
- Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
- Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
- Compressive phase retrieval: Optimal sample complexity with deep generative priors
- Riemannian thresholding methods for row-sparse and low-rank matrix recovery
- A VMiPG method for composite optimization with nonsmooth term having no closed-form proximal mapping
- An efficient asymptotic DC method for sparse and low-rank matrix recovery
- Joint structure-texture low-dimensional modeling for image decomposition with a plug-and-play framework
- Sparse recovery from quadratic measurements with external field
- Auto-calibration and biconvex compressive sensing with applications to parallel MRI
- Sharp optimality of sparse group LASSO and SLOPE under weaker assumptions
- Tensor train rank minimization with hybrid smoothness regularization for visual data recovery
- Convex relaxation algorithm for a structured simultaneous low-rank and sparse recovery problem
- Sparse disjointed recovery from noninflating measurements
This page was built for publication: Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978654)
