Exact matrix completion via convex optimization
The authors are concerned with recovering the data matrix from a sampling of its elements by solving a convex optimization problem. They first consider the case of low-rank matrices and prove that if the number \(m\) of sampled entries obeys \(m \geq Cn^{1.2}r \log n\) for some positive numerical constant \(C\), then with very high probability, most \(n\times n\) matrices of rank \(r\) can be perfectly recovered by solving a simple convex optimization problem. The authors show that the semidefinite program finds the matrix with minimum nuclear norm that fits the data. Replacing the exponent \(1.2\) by \(1.25\) gives that the result holds for all values of the rank. This interesting survey includes recent results on coherence and incoherence of linear subspaces of \(n\)-dimensional real space and on incoherence of unitary transformations by \textit{E. J. Candes, J. Romberg} [Inverse Probl. 23, No. 3, 969--985 (2007; Zbl 1120.94005)], on properties of sampling operator and on random orthogonal model. For a general discussion of approaches to convex optimization as well as specific technical results in the field, see the book by \textit{N. Shor} [Nondifferentiable Optimization and Polynomial Problems. Nonconvex Optimization and Its Applications. 24. Dordrecht: Kluwer Academic Publishers. (1998; Zbl 0901.49015)]. For a subspace \(U\) of dimension \(r\) of the \(n\)-dimensional real space and the orthogonal projection \({\mathcal P}_U\) onto \(U\), the authors of the paper define the coherence of \(U\) (vis-à-vis the standard basis \(({\mathbf e}_i)\)) as \[ \mu(U) \equiv \frac{n}{r} \max \| {\mathcal P}_U {\mathbf e}_i \|^2 . \] To state their main result, they introduce two assumptions about an \(n_1 \times n_2\) matrix \({\mathcal M}\) whose singular value decomposition is given by \({\mathcal M} = \sum_{1\leq k \leq r}\sigma_{k}{\mathbf u}_{k}{\mathbf v}^{*}_{k} \) and with column and row spaces denoted by \(U\) and \(V,\) respectively: (A0) The coherence obey \(\max(\mu(U), \mu(V)) \leq \mu_0\) for some positive \(\mu_0\). (A1) The \(n_1 \times n_2\) matrix \(\sum_{1\leq k \leq r}{\mathbf u}_{k}{\mathbf v}^{*}_{k} \) has a maximal entry bounded by \(\mu_1 \sqrt{r/(n_1 n_2)}\) in absolute value for some positive \(\mu_1\). Under these assumptions the main result of the paper asserts that if a matrix has row and column spaces that are incoherent with the standard basis, then the nuclear norm minimization can recover this matrix from a random sampling of a small number of entries \({\mathcal M}_{i j} \; (i,j) \in \Omega.\) The paper has eight sections: 1 Introduction. 2 Which Matrices Are Incoherent? 3 Duality. 4 Architecture of the Proof. 5 Connections with Random Graph Theory. 6 Proofs of the Critical Lemmas. 7 Numerical Experiments. 8 Discussion. The first one treats the problem of matrix completion via constraint minimization and justifies the author's choice of considering an alternative which minimizes the sum of nonvanishing singular values of the matrix \(X\) (the matrix nuclear norm \(\| X \|_{*}\)) over the constraint set (problem (1.5)): \[ \text{minimize } \| X \|_{*}\text{ subject to } X_{i j} = {\mathcal M}_{i j} \; (i,j) \in \Omega. \] The random orthogonal model and, more generally, matrices with incoherent column and row spaces are presented in Section 2. In Section 3 the authors establish sufficient conditions which guarantee that the true low-rank matrix \({\mathcal M}\) is the unique solution to problem (1.5). One of these conditions is the existence of a dual vector obeying two crucial properties. ``Section 4 constructs such a dual vector and provides the overall architecture of the proof which shows that, indeed, this vector obeys the desired properties provided that the number of measurements is sufficiently large. Surprisingly, as explored in Sect. 5, the existence of a dual vector certifying that \({\mathcal M}\) is unique is related to some problems in random graph theory including `the coupon collector's problem'. Following this discussion, we prove our main result via several intermediate results which are all proven in Sect. 6. Section 7 introduces numerical experiments showing that matrix completion based on nuclear norm minimization works well in practice. Section 8 closes the paper with a short summary of our findings, a discussion of important extensions and improvements. The appendix contains proofs of the fact (Theorem 4.2 from Section 4) that the operator \({\mathcal P}_{T} {\mathcal P}_{\Omega} {\mathcal P}_{T}\) (the product of projectors \({\mathcal P}_{T}\) onto the linear space \(T\) and the orthogonal projector \({\mathcal P}_{\Omega}\) onto the indices in the set \(\Omega\) of locations corresponding to the observed entries \({\mathcal M}_{i j}\)) does not deviate from its expected value in the part that follows from the concentration inequality of \textit{M. Talagrand} [Invent. Math. 126(3) 505--563 (1996; Zbl 0893.60001)], and the result on bounds of \(q\)th moment that is connected with the Schatten \(q\)-norm of a Rademacher series (Lemma 6.2 from Section 6). The proof of Lemma 6.2 is based on the noncommutative Khintchine inequality (Lemma 6.1 from Section 6) of \textit{F. Lust-Piquard} [C. R. Acad. Sci., Paris, Sér. I 303, 289--292 (1986; Zbl 0592.47038)] and \textit{A. Buchholz} [Math. Ann. 319, 1--16 (2001; Zbl 0991.46035)]. Some of the results and estimates used in proving the main theorem are of independent interest. There is a bibliography of about forty items.
- A Singular Value Thresholding Algorithm for Matrix Completion
- Adaptive estimation of a quadratic functional by model selection.
- Characterization of the subdifferential of some matrix norms
- Compressed sensing
- Concentration around the mean for maxima of empirical processes
- Decoding by Linear Programming
- Decoupling and Khintchine's inequalities for \(U\)-statistics
- Decoupling inequalities for the tail probabilities of multivariate \(U\)- statistics
- Fixed point and Bregman iterative methods for matrix rank minimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- New concentration inequalities in product spaces
- On the rank minimization problem over a positive semidefinite linear matrix inequality
- Operator Khintchine inequality in non-commutative probability
- Random vectors in the isotropic position
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sampling from large matrices
- Semidefinite Programming
- Sparsity and incoherence in compressive sampling
- Spectral analysis of data
- Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
- Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods
- The concentration of measure phenomenon
- The geometry of graphs and some of its algorithmic applications
- The mathematics of eigenvalue optimization
- The singular values of a Hadamard product: a basic inequality
- Theory of semidefinite programming for sensor network localization
- Leveraging mixed and incomplete outcomes via reduced-rank modeling
- Geometric median and robust estimation in Banach spaces
- Numerical comparisons between Bayesian and frequentist low-rank matrix completion: estimation accuracy and uncertainty quantification
- Latent variable graphical model selection via convex optimization
- Unitary dilation approach to contractive matrix completion.
- Asymptotic normality and optimalities in estimation of large Gaussian graphical models
- Multivariate GARCH estimation via a Bregman-proximal trust-region method
- Local block operators and TV regularization based image inpainting
- A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
- 1-bit matrix completion: PAC-Bayesian analysis of a variational approximation
- Global optimality condition and fixed point continuation algorithm for non-Lipschitz _p regularized matrix minimization
- Matrix completion via a low rank factorization model and an augmented Lagrangean succesive overrelaxation algorithm
- Stable analysis of compressive principal component pursuit
- Model-based co-clustering for ordinal data
- Matrix completion discriminant analysis
- Multi-view low-rank dictionary learning for image classification
- A patch-based low-rank tensor approximation model for multiframe image denoising
- Double instrumental variable estimation of interaction models with big data
- Low Tucker rank tensor recovery via ADMM based on exact and inexact iteratively reweighted algorithms
- Low-rank decomposition meets kernel learning: a generalized Nyström method
- Analysis of the equivalence relationship between \(l_{0}\)-minimization and \(l_{p}\)-minimization
- Random perturbation of low rank matrices: improving classical bounds
- A gradual rank increasing process for matrix completion
- The minimal measurement number for low-rank matrix recovery
- Proximal iteratively reweighted algorithm for low-rank matrix recovery
- Exact recovery of sparse multiple measurement vectors by \(l_{2,p}\)-minimization
- \(\ell _p\) regularized low-rank approximation via iterative reweighted singular value minimization
- Affine matrix rank minimization problem via non-convex fraction function penalty
- Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization
- Adaptive confidence sets for matrix completion
- Painless breakups -- efficient demixing of low rank matrices
- Matrix completion with \(\varepsilon\)-algorithm. In memory of Peter Wynn (1931--2017)
- A new nonconvex approach to low-rank matrix completion with application to image inpainting
- An improved method of training overcomplete dictionary pair
- Matrix factorization for evolution data
- Robust missing traffic flow imputation considering nonnegativity and road capacity
- Linear total variation approximate regularized nuclear norm optimization for matrix completion
- Enhancing matrix completion using a modified second-order total variation
- A new piecewise quadratic approximation approach for \(L_0\) norm minimization problem
- Alternating direction method of multipliers for generalized low-rank tensor recovery
- Statistical inference of semidefinite programming
- Robust covariance estimation for approximate factor models
- The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion
- A decoupled method for image inpainting with patch-based low rank regulariztion
- Structured volatility matrix estimation for non-synchronized high-frequency financial data
- Learning semidefinite regularizers
- Noise-tolerance matrix completion for location recommendation
- Low-rank matrix recovery using Gabidulin codes in characteristic zero
- Manifold based low-rank regularization for image restoration and semi-supervised learning
- A mixture of nuclear norm and matrix factorization for tensor completion
- Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics
- On the singular values of matrices with high displacement rank
- Robust bilinear factorization with missing and grossly corrupted observations
- DC formulations and algorithms for sparse optimization problems
- Tensor completion using total variation and low-rank matrix factorization
- Overcoming human trafficking via operations research and analytics: opportunities for methods, models, and applications
- Matrix completion under interval uncertainty
- Low-rank matrix completion using nuclear norm minimization and facial reduction
- Equivalent Lipschitz surrogates for zero-norm and rank optimization problems
- Block tensor train decomposition for missing data estimation
- Templates for convex cone problems with applications to sparse signal recovery
- Error bounds for rank constrained optimization problems and applications
- Robust group lasso: model and recoverability
- Flexible low-rank statistical modeling with missing data and side information
- Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization
- The convex geometry of linear inverse problems
- TILT: transform invariant low-rank textures
- Compressed sensing and matrix completion with constant proportion of corruptions
- Discussion: Latent variable graphical model selection via convex optimization
- Rejoinder: Latent variable graphical model selection via convex optimization
- Complex-valued autoencoders
- A note on element-wise matrix sparsification via a matrix-valued Bernstein inequality
- Accelerated linearized Bregman method
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Non-asymptotic approach to varying coefficient model
- Second order accurate distributed eigenvector computation for extremely large matrices
- Rank penalized estimators for high-dimensional matrices
- Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations
- Exact matrix completion based on low rank Hankel structure in the Fourier domain
- An efficient method for non-negative low-rank completion
- On the estimation of unknown distances for a class of Euclidean distance matrix completion problems with interval data
- Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion
- A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrix
- Iterative adaptive nonconvex low-rank tensor approximation to image restoration based on ADMM
- On the subdifferential of symmetric convex functions of the spectrum for symmetric and orthogonally decomposable tensors
- On polynomial time methods for exact low-rank tensor completion
- Matrix factorization for multivariate time series analysis
- Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
- On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems
- Online optimization for max-norm regularization
- A general self-adaptive relaxed-PPA method for convex programming with linear constraints
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Penalized semidefinite programming for quadratically-constrained quadratic optimization
- Tensor \(N\)-tubal rank and its convex relaxation for low-rank tensor recovery
- Tensor completion via bilevel minimization with fixed-point constraint to estimate missing elements in noisy data
- An accelerated IRNN-iteratively reweighted nuclear norm algorithm for nonconvex nonsmooth low-rank minimization problems
- Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten p-norms
- Riemannian gradient descent methods for graph-regularized matrix completion
- Quartic first-order methods for low-rank minimization
- Low-rank matrix completion in a general non-orthogonal basis
This page was built for publication: Exact matrix completion via convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2655288)
