A Simpler Approach to Matrix Completion

zbMath1280.68141arXiv0910.0651MaRDI QIDQ5396731

Benjamin Recht

Publication date: 3 February 2014

Full work available at URL: https://arxiv.org/abs/0910.0651

zbMATH Keywords

convex optimizationmatrix completionrandom matricescompressed sensingnuclear norm minimizationlow-rank matricesoperator Chernoff bound

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Nonconvex programming, global optimization (90C26) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (only showing first 100 items - show all)

Heteroskedastic PCA: algorithm, optimality, and applications ⋮ A shrinkage principle for heavy-tailed data: high-dimensional robust low-rank matrix recovery ⋮ 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 ⋮ Low-rank diffusion matrix estimation for high-dimensional time-changed Lévy processes ⋮ Optimal large-scale quantum state tomography with Pauli measurements ⋮ A quadratically convergent algorithm for structured low-rank approximation ⋮ Relaxed leverage sampling for low-rank matrix completion ⋮ A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm ⋮ Matrix completion via max-norm constrained optimization ⋮ Sublinear time algorithms for approximate semidefinite programming ⋮ Lifting for Blind Deconvolution in Random Mask Imaging: Identifiability and Convex Relaxation ⋮ A rank-corrected procedure for matrix completion with fixed basis coefficients ⋮ Tensor Completion in Hierarchical Tensor Representations ⋮ On tensor completion via nuclear norm minimization ⋮ A graphical approach to the analysis of matrix completion ⋮ Parallel stochastic gradient algorithms for large-scale matrix completion ⋮ Deterministic algorithms for matrix completion ⋮ Matrix completion discriminant analysis ⋮ On statistics, computation and scalability ⋮ Guarantees of Riemannian optimization for low rank matrix completion ⋮ Optimal prediction in the linearly transformed spiked model ⋮ Rank-constrained optimization and its applications ⋮ Image completion and blind deconvolution: model and algorithm ⋮ Double instrumental variable estimation of interaction models with big data ⋮ An alternating minimization method for matrix completion problems ⋮ Local convergence of an algorithm for subspace identification from partial data ⋮ Matrix completion by singular value thresholding: sharp bounds ⋮ Nonsmooth rank-one matrix factorization landscape ⋮ Empirical Bayes matrix completion ⋮ Unnamed Item ⋮ Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution ⋮ Compressed sensing and matrix completion with constant proportion of corruptions ⋮ Matrix completion with nonconvex regularization: spectral operators and scalable algorithms ⋮ Matrix completion with sparse measurement errors ⋮ 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 ⋮ Flavors of Compressive Sensing ⋮ Adaptive confidence sets for matrix completion ⋮ Asymptotic equivalence of quantum state tomography and noisy matrix completion ⋮ Von Neumann entropy penalization and low-rank matrix estimation ⋮ Noisy low-rank matrix completion with general sampling distribution ⋮ The space decomposition theory for a class of eigenvalue optimizations ⋮ Guaranteed clustering and biclustering via semidefinite programming ⋮ Matrix concentration inequalities via the method of exchangeable pairs ⋮ On the spectra of general random mixed graphs ⋮ An introduction to a class of matrix cone programming ⋮ Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion ⋮ Cross: efficient low-rank tensor completion ⋮ Stable rank-one matrix completion is solved by the level \(2\) Lasserre relaxation ⋮ Exact matrix completion based on low rank Hankel structure in the Fourier domain ⋮ Noise-tolerance matrix completion for location recommendation ⋮ A modified augmented Lagrange multiplier algorithm for Toeplitz matrix completion ⋮ Max-norm optimization for robust matrix recovery ⋮ Concentration inequalities for matrix martingales in continuous time ⋮ Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion ⋮ Robust matrix completion ⋮ Finding a low-rank basis in a matrix subspace ⋮ Degrees of freedom in low rank matrix estimation ⋮ Convergence of projected Landweber iteration for matrix rank minimization ⋮ User-friendly tail bounds for sums of random matrices ⋮ Ranking and Sparsifying a Connection Graph ⋮ On polynomial time methods for exact low-rank tensor completion ⋮ Estimation of high-dimensional low-rank matrices ⋮ Some empirical advances in matrix completion ⋮ Unnamed Item ⋮ Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix ⋮ Layer-wise pre-training low-rank NMF model for mammogram-based breast tumor classification ⋮ Low-rank matrix completion in a general non-orthogonal basis ⋮ Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach ⋮ Estimation in High Dimensions: A Geometric Perspective ⋮ Ranking recovery from limited pairwise comparisons using low-rank matrix completion ⋮ Collaborative filtering with information-rich and~information-sparse entities ⋮ New applications of matrix methods ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ Practical matrix completion and corruption recovery using proximal alternating robust subspace minimization ⋮ Active matrix factorization for surveys ⋮ Matrix optimization based Euclidean embedding with outliers ⋮ The spectra of multiplicative attribute graphs ⋮ Fast global convergence of gradient methods for high-dimensional statistical recovery ⋮ Superresolution 2D DOA estimation for a rectangular array via reweighted decoupled atomic norm minimization ⋮ Guarantees of Riemannian Optimization for Low Rank Matrix Recovery ⋮ Matrix completion for cost reduction in finite element simulations under hybrid uncertainties ⋮ Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence ⋮ Efficient Matrix Sensing Using Rank-1 Gaussian Measurements ⋮ An adaptation for iterative structured matrix completion ⋮ Recovering PCA from Hybrid-$(\ell_1,\ell_2)$ Sparse Sampling of Data Elements ⋮ Unnamed Item ⋮ Tensor Methods for Nonlinear Matrix Completion ⋮ Rapid, robust, and reliable blind deconvolution via nonconvex optimization ⋮ On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint ⋮ Stable als approximation in the TT-format for rank-adaptive tensor completion ⋮ 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 ⋮ ROP: matrix recovery via rank-one projections ⋮ Unnamed Item ⋮ A mean value algorithm for Toeplitz matrix completion ⋮ Proof methods for robust low-rank matrix recovery ⋮ Loose laplacian spectra of random hypergraphs

This page was built for publication: A Simpler Approach to Matrix Completion