Incoherence-Optimal Matrix Completion

DOI10.1109/TIT.2015.2415195MaRDI QIDQ2978655zbMATH OpenOpenAlexFDO

Authors Yudong Chen

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Matrix completion problems (15A83) Numerical linear algebra (65F99) Analysis of algorithms and problem complexity (68Q25)

Abstract: This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence parameter (as well as to the rank $r$ and the matrix dimension $n$ up to a log factor). As a consequence, we improve the sample complexity of recovering a semidefinite matrix from $O(n{r}^{2}lo{g}^{2}n)$ to $O(nrlo{g}^{2}n)$, and the highest allowable rank from $Theta(sqrtn/logn)$ to $Theta(n/lo{g}^{2}n)$. The key step in proof is to obtain new bounds on the $el{l}_{infty,2}$-norm, defined as the maximum of the row and column norms of a matrix. To illustrate the applicability of our techniques, we discuss extensions to SVD projection, structured matrix completion and semi-supervised clustering, for which we provide order-wise improvements over existing results. Finally, we turn to the closely-related problem of low-rank-plus-sparse matrix decomposition. We show that the joint incoherence condition is unavoidable here for polynomial-time algorithms conditioned on the Planted Clique conjecture. This means it is intractable in general to separate a rank-$omega(sqrtn)$ positive semidefinite matrix and a sparse matrix. Interestingly, our results show that the standard and joint incoherence conditions are associated respectively with the information (statistical) and computational aspects of the matrix decomposition problem.

Cited in

(36)

• Enhancing matrix completion using a modified second-order total variation
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Robust non-parametric regression via incoherent subspace projections
• Proof methods for robust low-rank matrix recovery
• Tensor clustering with planted structures: statistical optimality and computational limits
• Computational barriers to estimation from low-degree polynomials
• Guarantees of Riemannian optimization for low rank matrix completion
• 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
• Optimal testing for planted satisfiability problems
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach
• Efficient matrix sensing using rank-1 Gaussian measurements
• Rank-Sparsity Incoherence for Matrix Decomposition
• Low rank matrix recovery from rank one measurements
• An \(\ell_{\infty}\) eigenvector perturbation bound and its application
• Low-Rank Matrix Completion in the Presence of High Coherence
• Matrix completion and related problems via strong duality
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
• Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent
• On the simplicity and conditioning of low rank semidefinite programs
• Streaming principal component analysis from incomplete data
• Non-convex matrix completion and related problems via strong duality
• Importance sampling in signal processing applications
• Tensor completion by multi-rank via unitary transformation
• Iterative tensor eigen rank minimization for low-rank tensor completion
• Cryptography from planted graphs: security with logarithmic-size messages
• Grouped tensor low-rank representation for multi-dimensional image recovery
• Rank-sparsity decomposition for planted quasi clique recovery
• Structured matrix learning under arbitrary entrywise dependence and estimation of Markov transition kernel
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Robust Matrix Completion with Heavy-Tailed Noise
• Adaptive sampling with tensor leverage scores for exact low-rank third-order tensor completion
• Nonconvex deterministic matrix completion by projected gradient descent methods

This page was built for publication: Incoherence-Optimal Matrix Completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978655)