A simpler approach to matrix completion
From MaRDI portal
Abstract: This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.
Recommendations
Cited in
(only showing first 100 items - show all)- Low-rank diffusion matrix estimation for high-dimensional time-changed Lévy processes
- A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
- Matrix completion discriminant analysis
- Double instrumental variable estimation of interaction models with big data
- Adaptive confidence sets for matrix completion
- Cross: efficient low-rank tensor completion
- Noise-tolerance matrix completion for location recommendation
- Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization
- Compressed sensing and matrix completion with constant proportion of corruptions
- Accelerated linearized Bregman method
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Rank penalized estimators for high-dimensional matrices
- Exact matrix completion based on low rank Hankel structure in the Fourier domain
- Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion
- On polynomial time methods for exact low-rank tensor completion
- Low-rank matrix completion in a general non-orthogonal basis
- Ranking recovery from limited pairwise comparisons using low-rank matrix completion
- New applications of matrix methods
- Active matrix factorization for surveys
- Matrix optimization based Euclidean embedding with outliers
- Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
- An adaptation for iterative structured matrix completion
- On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
- On the robustness of minimum norm interpolators and regularized empirical risk minimizers
- Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion
- Proof methods for robust low-rank matrix recovery
- Heteroskedastic PCA: algorithm, optimality, and applications
- Guarantees of Riemannian optimization for low rank matrix completion
- Optimal prediction in the linearly transformed spiked model
- An alternating minimization method for matrix completion problems
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
- On the spectra of general random mixed graphs
- Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation
- Convergence of projected Landweber iteration for matrix rank minimization
- Layer-wise pre-training low-rank NMF model for mammogram-based breast tumor classification
- Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
- Superresolution 2D DOA estimation for a rectangular array via reweighted decoupled atomic norm minimization
- Matrix completion for cost reduction in finite element simulations under hybrid uncertainties
- Rapid, robust, and reliable blind deconvolution via nonconvex optimization
- Stable als approximation in the TT-format for rank-adaptive tensor completion
- ROP: matrix recovery via rank-one projections
- Matrix estimation by universal singular value thresholding
- A mean value algorithm for Toeplitz matrix completion
- Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery
- Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction
- Parallel stochastic gradient algorithms for large-scale matrix completion
- Rank-constrained optimization and its applications
- Empirical Bayes matrix completion
- Asymptotic equivalence of quantum state tomography and noisy matrix completion
- Noisy low-rank matrix completion with general sampling distribution
- Matrix concentration inequalities via the method of exchangeable pairs
- An introduction to a class of matrix cone programming
- Collaborative filtering with information-rich and~information-sparse entities
- Relaxed leverage sampling for low-rank matrix completion
- Exact matrix completion via convex optimization
- Image completion and blind deconvolution: model and algorithm
- Nonsmooth rank-one matrix factorization landscape
- Matrix completion with sparse measurement errors
- Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
- Estimation in high dimensions: a geometric perspective
- Probabilistic low-rank matrix completion from quantized measurements
- Guarantees of Riemannian optimization for low rank matrix recovery
- Optimal large-scale quantum state tomography with Pauli measurements
- Efficient matrix sensing using rank-1 Gaussian measurements
- A quadratically convergent algorithm for structured low-rank approximation
- Fast and near-optimal matrix completion via randomized basis pursuit
- Deterministic algorithms for matrix completion
- Matrix completion via max-norm constrained optimization
- Sublinear time algorithms for approximate semidefinite programming
- Uniqueness of low-rank matrix completion by rigidity theory
- A rank-corrected procedure for matrix completion with fixed basis coefficients
- Loose Laplacian spectra of random hypergraphs
- On tensor completion via nuclear norm minimization
- A graphical approach to the analysis of matrix completion
- Lifting for blind deconvolution in random mask imaging: identifiability and convex relaxation
- Tensor completion in hierarchical tensor representations
- On statistics, computation and scalability
- Uniqueness conditions for low-rank matrix recovery
- Von Neumann entropy penalization and low-rank matrix estimation
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- The space decomposition theory for a class of eigenvalue optimizations
- Local reconstruction of low-rank matrices and subspaces
- Flavors of compressive sensing
- Using side information to reliably learn low-rank matrices from missing and corrupted observations
- Recovering PCA and sparse PCA via hybrid-(_1,_2) sparse sampling of data elements
- Matrix completion with noisy entries and outliers
- Guaranteed clustering and biclustering via semidefinite programming
- Ranking and sparsifying a connection graph
- Matrix completion and related problems via strong duality
- Recovering structured probability matrices
- Tensor methods for nonlinear matrix completion
- Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
- Computing large market equilibria using abstractions
- A modified augmented Lagrange multiplier algorithm for Toeplitz matrix completion
- Matrix Completion under Low-Rank Missing Mechanism
- Color image inpainting via robust pure quaternion matrix completion: error bound and weighted loss
- WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- GNMR: a provable one-line algorithm for low rank matrix recovery
This page was built for publication: A simpler approach to matrix completion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5396731)
