Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

By Sahand N. Negahban, Martin J. Wainwright. 2010

546 citations recorded by the source corpus.

We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniformentrywise sampling as a special case. We analyze the associated random observation operator, and prove that with high probability, it satisfies a form of restricted strong convexity with respect to weighted Frobenius norm. Using this property, we obtain as corollaries a number of error bounds on matrix completion in the weighted Frobenius norm under noisy sampling and for both exact and near low-rank matrices. Our results are based on measures of the 'spikiness' and 'low-rankness' of matrices that are less restrictive than the incoherence conditions imposed in previous work. Our technique involves an M-estimator that includes controls on both the rank and spikiness of the solution, and we establish non-asymptotic error bounds in weighted Frobenius norm for recovering matrices lying with lq-"balls" of bounded spikiness. Using information-theoretic methods, we show that no algorithm can achieve better estimates (up to a logarithmic factor) over these same sets, showing that our conditions on matrices and associated rates are essentially optimal.

Subfields: Statistics and Probability, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Mathematical Optimization

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “We also mention [Negahban and Wainwright, 2012] who consider random sampling, but one that is not uniformly random across the entries.”
Principal Components and Regularized Estimation of Factor Models (2017, background): “t perspectives to a related problem. 12For application of the incoherence condition in matrix completion, see Candes et al. (2011). For general matrix recovery problems, see Agarwal et al. (2012) and Negahban and Wainwright (2012), . 13 4.1 Robust Principal Components (RPCA):(F,Λ) This subsection co”
Geometric median and robust estimation in Banach spaces (2013, background): “Results in this direction can be found in [10,24,32,40], to name a few.”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, neutral): “Using a different proof framework, reference [8] provided theoretical guarantee for a variant of the formulation (3).”
Estimation of (near) low-rank matrices with noise and high-dimensional scaling (2009, unknown): “We have thus shown that ∆ = 0, which implies that Θ = Θ ∗ as claimed.”
Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems (2019, methodology): “Like [37], we assume that probability matrix Q is rank-1: Q ij = π i ρ j for some n -dimensional and m -dimensional probability vectors π and ρ , respectively.”
Matrix Completion on Graphs (2014, background): “2 r log n for n × n matrices of rank r (this bound has been reﬁned more recently, see [22] and references therein). of The case noisy observations was studied in [7, 19], and the non-uniform sampling setting was considered in [23].”
On factor models with random missing: EM estimation, inference, and cross validation (2020, unknown): “A similar condition is also imposed in Negahban and Wainwright (2012). Since ‖ũr‖2 = ‖ṽr‖2 = 1, on average each entry of ũrṽ′ r is of the order (NT ) −1/2.”
Fast global convergence of gradient methods for high-dimensional statistical recovery (2011, background): “For the case of matrix completion, the paper [9] establishes a form of RSC useful for controlling statistical error; this argument can be suitably modified to establish related notions of RSC/RSM required for ensuring fast algorithmic convergence.”
Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing (2011, background): “Recently, Negahban and Wainwright (2010) studied the problem of matrix completion under a non-uniform distribution.”
Robust matrix completion (2014, background): “tuation in applications corresponds to the noisy setting in which the few available entries are corrupted by noise. Noisy matrix completion has been in the focus of several recent studies (see, e.g., [16, 23, 19, 21, 12, 17, 5]). The matrix completion problem is motivated by a variety of application”
Statistical Learning with Sparsity: The Lasso and Generalizations (2015, methodology): “Our discussion of the Bayesian Lasso is based on Park and Casella (2008). The bootstrap is due to Efron (1979); the book by Efron and Tibshirani (1993) is a comprehensive reference.”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, result): “Thirdly, while our results do not directly apply to settings where the population risk is not strongly convex, our results are still important for the following two-fold reasons: (1) while many learning problems are highly non-convex globally, they sometimes satisfy certain restricted strong convexi”
Canonical Tensor Decomposition for Knowledge Base Completion (2018, background): “The weighted trace norm reweights elements of the factors based on the marginal rows and columns sampling probabilities, which can improve sample complexity bounds when sampling is non-uniform (Foygel et al., 2011; Negahban & Wainwright, 2012).”