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

Sahand Negahban; Martin J. Wainwright

Source-linked AI summary

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

Sahand Negahban, Martin J. Wainwright

arXiv:1009.2118v2Sep 10, 2010cs.ITmath.ST

TL;DR

Noisy matrix completion lacks established restricted strong convexity guarantees under weighted sampling. The paper proves such a guarantee and derives weighted-Frobenius error bounds for general, exact low-rank, and approximately low-rank matrices, with rates that are minimax-optimal up to logarithmic factors.

Problem
The paper addresses whether restricted strong convexity can hold for noisy matrix completion, enabling non-asymptotic recovery guarantees beyond restrictive matrix conditions.
Method
The analysis combines restricted strong convexity for controlled-rank, bounded-spikiness matrices with an M-estimator controlling nuclear norm and entrywise magnitude.
Results
With high probability, the sampling operator satisfies restricted strong convexity and yields weighted-Frobenius error bounds for general, exactly low-rank, and approximately low-rank matrices.
Takeaways & Limitations
The resulting recovery rates are minimax-optimal up to logarithmic factors over the considered bounded-spikiness matrix classes.
Takeaways & Limitations
The sampling model is limited to settings where each row or column is sampled with a specified probability, not entry-specific probabilities.

Abstract

from arXiv · show

We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniform entrywise 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 $\ell_q$-"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.

1 Introduction

The paper studies low-rank and near low-rank matrix completion from noisy partial observations. Its main contribution is proving a high-probability restricted strong convexity condition and using it to derive weighted Frobenius-norm recovery bounds.

1 Introduction: The problem concerns reconstructing low-rank or near low-rank matrices from noisy observations of a subset of entries.The setting generalizes exact matrix completion with uncorrupted observations to noisy sampling.
1 Introduction: The proposed approximate recovery method uses an M-estimator combining a data term with a weighted nuclear norm regularizer.The nuclear norm is defined as the sum of a matrix’s singular values.
1 Introduction: With high probability, Theorem 1 proves that the matrix completion loss function satisfies restricted strong convexity over the set C.This addresses whether an appropriate RSC condition holds in the matrix completion setting.
1 Introduction: Theorem 2 derives a non-asymptotic recovery error bound in weighted Frobenius norm for general matrices.The result is then specialized to exactly low-rank and near low-rank matrices.

2 Background and problem formulation

The section formulates noisy low-rank matrix completion under uniform and weighted sampling, then introduces an equivalent observation-operator representation. It explains why restricted curvature requires excluding spiky matrices and motivates weighted spikiness and low-rankness measures.

2.1 Uniform and weighted sampling models: The problem concerns recovering an unknown matrix Θ∗∈R^(d_r×d_c) from n i.i.d. noisy entry observations.
2.1 Uniform and weighted sampling models: Uniform sampling selects row and column indices independently and uniformly, while weighted sampling uses row and column distributions R/d_r and C/d_c.
2.1 Uniform and weighted sampling models: Every row and column has positive sampling probability bounded below by 1/L, without requiring the weights to remain bounded as dimensions grow.
2.2 The observation operator and restricted strong convexity: The statistically equivalent reformulation writes observations as y_i=⟨⟨X^(i),Θ∗⟩⟩+νξ_i and vectorizes them as y=X_n(Θ∗)+νξ.
2.2 The observation operator and restricted strong convexity: The observation operator maps each matrix Θ to an n-vector of sampled inner products, with the weighted Frobenius norm determined by the row and column weights.
2.2 The observation operator and restricted strong convexity: When n≪d_rd_c, restricted-curvature bounds cannot hold uniformly over all matrices, even under rank constraints.
2.2 The observation operator and restricted strong convexity: A rank-one matrix concentrated at a single entry violates the desired condition with high probability because that entry is unlikely to be observed.
2.3 Controlling the spikiness and rank: The paper therefore measures spikiness by comparing weighted ℓ∞ and weighted Frobenius norms, using a scale-invariant ratio satisfying 1≤α_sp(Θ)≤√(d_rd_c).

3 Main results and their consequences

The paper proves restricted strong convexity for weighted matrix sampling under bounded spikiness and low-rankness, derives noisy recovery bounds for exact and near low-rank matrices, and shows these rates are minimax-optimal up to logarithmic factors.

3.1 Restricted strong convexity: Restricted strong convexity holds for sampling directions whose spikiness and rank measures are not overly large, once n exceeds a constant multiple of d log d.The condition implies the quadratic loss is strongly convex on a restricted set of directions.
3.2 Noisy matrix completion: The weighted M-estimator combines a weighted nuclear-norm penalty with an ℓ∞-norm constraint to control low-rankness and spikiness.The resulting error bound separates rank-r estimation error from approximation error.
3.2 Noisy matrix completion: For exactly low-rank targets with sub-exponential noise, the recovery rate reflects roughly r(dr + dc) free parameters, up to logarithmic factors.The bound includes ν^2 ∨ 1, so exact recovery is not obtained merely by letting ν approach zero under the stated spikiness condition.
3.2 Noisy matrix completion: For near low-rank matrices in ℓq-balls with bounded spikiness, the rate generalizes the exact-rank result but has exponent 1 − q/2 instead of 1.The exact-rank case is recovered when q = 0 through an effective rank choice.
3.3 Minimax lower bounds: The minimax lower bound matches the upper bounds for exact and near low-rank classes up to logarithmic factors in matrix dimension d, so no estimator performs substantially better.The lower-bound argument is constructive and applies to matrices that are near low-rank and not overly spiky.

4 Proofs for noisy matrix completion

The proofs reduce weighted matrix completion to an equivalent transformed problem, then establish the noisy upper bound through a constrained estimator and error decomposition. A matching lower bound is obtained by packing arguments, Fano’s inequality, and information-theoretic testing.

Change of variables: The transformation Θ 7→Γ preserves the observation model while converting weighted Frobenius, nuclear, and infinity norms into ordinary norms.The modified operator uses e_X(i) := R^-1/2 X(i) C^-1/2 and satisfies X_n′(Γ) = X_n(Θ).
Proof of Theorem 2: Theorem 2 is proved by decomposing the estimator’s error into components aligned with the singular subspaces of Γ∗ and analyzing cases based on membership in C′(n; c0).The argument combines a nuclear-norm bound, a basic inequality, and the reformulated restricted lower bound.
Proof of Theorem 2: With high probability, one of bounds (32), (33), or (35) holds, and these cases combine into a universal-constant upper bound for the estimator.The proof summarizes the three-case analysis using α∗ ≥ 1.
Proof of Corollary 1: Corollary 1’s proof selects r by thresholding the singular values of Γ∗ and chooses τ = α∗λ∗ to optimize the resulting upper bound.The selected rank is r = max{j | σ_j(Γ∗) > τ}.
Proof of Theorem 3: The lower bound reduces estimation to multiway testing over a separated packing set, applies Fano’s inequality under Gaussian noise, and concludes a minimax error lower bound.The packing contains rank-r matrices with prescribed Frobenius separation and spikiness-related constraints.

5 Proof of Theorem 1

The proof establishes Theorem 1 by controlling a bad event for the sampling operator and deriving its tail bound through fixed-radius analysis, peeling, and discretization. It first treats the case d_r = d_c, which changes only constant factors relative to the general setting.

Dimension reduction: The proof assumes d_r = d_c as a worst-case simplification, replacing both dimensions by max{d_r, d_c} and affecting only constant factors.The general case d_r ≠ d_c can be handled by appropriate modifications when those constants matter.
Bad-event control: Theorem 1 follows once the bad event is shown to satisfy P[E(X_n′)] ≤ 16 exp(−c′d log d).The proof reformulates the theorem as a high-probability statement and studies the complementary bad event.
Radius decomposition: A peeling argument reduces control of E(X_n′) to bounding simpler events E(X_n′; D) separately for each fixed radius D > 0.Rescaling permits the assumption ||Γ||∞ = 1, while D = |||Γ|||F and ρ = |||Γ|||1 parameterize the remaining degrees of freedom.
Discretization: For fixed D, the proof uses a δ-covering of B(D), controls the covering-set maximum and residual term, and chooses δ = D/8.These bounds combine through the upper bound (49) to establish the required tail bound (48).
Conclusion: The resulting tail bound satisfies Lemma 3’s condition and completes the proof of Theorem 1.The argument concludes after combining the two auxiliary lemmas with the covering-based upper bound.

6 Discussion

The paper establishes weighted matrix-completion error bounds from restricted strong convexity, covering general, exactly low-rank, and approximately low-rank matrices under partial noisy observations. Open questions include sampling models with entry-specific probabilities beyond row- or column-level sampling.

Contributions: The paper establishes error bounds for weighted matrix completion from partial and noisy observations.The results include a general bound applying to any matrix.
Contributions: The general result yields corollaries for exactly low-rank and approximately low-rank matrices.These corollaries follow from the paper’s general weighted matrix-completion result.
Contributions: A key technical result proves restricted strong convexity for the matrix sampling operator over matrices with controlled rank and spikiness.This property underlies the paper’s error-bound results.
Open questions: The analysis covers uniform and non-uniform sampling when each row or column is sampled with a specified probability.It does not cover sampling probabilities that differ from entry to entry.
Open questions: Entry-specific sampling probabilities remain an open extension, motivated by empirical work on such sampling schemes.The passage identifies this as a setting investigated empirically by Salakhutdinov and Srebro.

A Proof of Lemma 2

The proof uses a probabilistic construction of random low-rank matrices, then shows that with probability at least 1/2 a subset of size M = M′/4 satisfies the required properties. Unitary invariance, concentration bounds, and a final event argument establish the construction’s norm and separation guarantees.

Random construction: Random matrices are generated by sampling structured entries, extending them with zero rows, and applying a random unitary transformation before rescaling.The construction defines eΘℓ, then sets Θℓ using a random unitary matrix Q and a rescaling factor.
Subset existence: With probability at least 1/2, the random collection contains a subset of size M = M′/4 satisfying properties (a) through (d).The proof analyzes the random set and reduces the result to finding a sufficiently large subset with the required properties.
Norm and separation bounds: The construction gives each unscaled matrix rank at most r, while unitary invariance preserves the rescaled matrices’ Frobenius norm at δ.The proof also uses unitary invariance to transfer pairwise Frobenius-distance calculations to the unscaled matrices.
Norm and separation bounds: Hoeffding’s bound controls pairwise matrix distances by applying concentration to a sum of rd independent bounded variables and then taking a union bound over pairs.The variables are bounded by 4, their sum has mean 2, and there are fewer than (M′)^2 pairs.
Properties (c) and (d): Bounds on spikiness and operator norm are combined for each fixed matrix, and the resulting estimate supports the final subset-existence event.The operator-norm step uses the representation involving a random Rademacher matrix and known sub-Gaussian matrix bounds.
Conclusion: Because M < M′/2, the event that a subset of cardinality M exists has probability at least 1/2, completing the proof.This conclusion follows from the bound on the event E.

B Proof of Lemma 3

The proof partitions any violating matrix into a set S_ℓ, establishes the corresponding event E(X_n′; α_ℓμ), and then applies a union bound over ℓ.

Set decomposition: Any matrix Γ for which E(X_n′) holds must belong to some set S_ℓ.This set-based reduction is the starting point for controlling violating matrices.
Set decomposition: For Γ ∈ S_ℓ, there exists a matrix Γ ∈ B(α_ℓμ) satisfying the required construction.The passage states this existence guarantee for each set S_ℓ.
Event implication: When the violating matrix belongs to S_ℓ, the event E(X_n′; α_ℓμ) must hold.The argument uses α = 7/6 in deriving the final equality.
Union bound: Because every violating matrix lies in some S_ℓ, a union bound completes the probability control.The proof explicitly invokes the union bound after establishing the event implication for each ℓ.

C Proof of Lemma 4

The proof of Lemma 4 derives a fixed-matrix tail bound and a covering-number bound, then combines them via a union bound to establish the lemma for sufficiently large d.

Conclusion: For any fixed c0, the final inequality holds once log d is sufficiently large, and choosing c0 sufficiently large extends it to all d ≥2.The proof notes that terms involving D2 and n cancel.
Proof structure: The proof reduces Lemma 4 to establishing the intermediate tail bound (57) and covering-number bound (58).These bounds are then combined with a union bound.
Upper bounding the covering number (58): The covering-number bound (58) follows by projecting a Frobenius-norm δ-cover of the nuclear norm ball onto the constrained set.Non-expansiveness of projection onto a non-empty, closed, convex set preserves the δ-cover.
Upper bounding the covering number (58): The ambient nuclear-norm-ball covering number is upper bounded using Sudakov minoration, nuclear/operator-norm duality, and Gaussian operator-norm estimates.This establishes bound (58).
Establishing the tail bound (57): For the tail bound, the operator expression is represented using zero-mean variables Y_i = ⟨⟨e X(i), Γ⟩⟩, each bounded by 2L.A concentration result from Ledoux is applied to complete the bound (57).

D Proof of Lemma 5

The proof of Lemma 5 bounds the target function by first establishing concentration around its expectation and then controlling that expectation. It combines bounded differences, contraction, norm duality, and an operator-norm bound, yielding the conclusion when n = Ω(d log d).

Concentration: The argument first proves concentration of G around E[G(Xn′)] using a bounded-difference inequality for the symmetric function G.The proof compares samples differing in one coordinate and then applies the bounded-differences form of the Azuma–Hoeffding inequality.
Concentration: Changing one sampling matrix affects at most two entries, each bounded by 2Ld, which gives |G(Xn′) − G(g Xn′)| ≤ 4L.The same argument with the two inputs interchanged establishes the absolute-difference bound.
Expectation bound: The expectation is bounded using Jensen’s inequality, Rademacher contraction, and duality between operator and nuclear norms.The contraction step uses |⟨⟨e X(i), ∆⟩⟩| ≤ 2L for every i.
Expectation bound: Lemma 6 supplies the remaining upper bound on the expected operator norm.The proof invokes this auxiliary result after reducing the expectation bound to an operator-norm term.
Conclusion: n = Ω(d log d) is sufficient, together with the earlier bound (60), to complete the proof of Lemma 5.The final concentration conclusion follows after substituting the relevant constant choice into bound (59).

E Proof of Lemma 6

The proof of Lemma 6 applies an Ahlswede–Winter matrix bound to centered random matrices Y^(i) and computes the quantities required by Lemma 7. The resulting tail bound is then integrated using the expectation identity for nonnegative random variables, with L ≥ 1 used in the final inequality.

Proof of Lemma 6: The proof applies an Ahlswede–Winter matrix bound to Y^(i) := ε_i e X^(i), which is zero-mean and bounded.This setup supplies the random-matrix quantities needed for Lemma 7.
Proof of Lemma 6: The quantities σ_i required by Lemma 7 are computed before applying that lemma to obtain a tail bound.The passage does not include the displayed formulas for σ_i or the tail probability.
Proof of Lemma 6: The proof converts the tail bound into an expectation using E[T] for nonnegative random variables, and the second inequality relies on L ≥ 1.The supplied passages show the integration step and identify the condition used for the inequality.

F Ahlswede-Winter matrix bound

This section states a Bernstein version of the Ahlswede–Winter tail bound for the operator norm of sums of independent random matrices, under boundedness or sub-exponential assumptions.

F Ahlswede-Winter matrix bound: The stated Ahlswede–Winter bound controls the operator norm of a sum of independent, zero-mean random matrices.The version is a slight weakening of a result due to Recht but is sufficient for the paper’s purposes.
F Ahlswede-Winter matrix bound: The matrices may satisfy the uniform bound ||Y^(i)||_2 ≤ M.The matrices are independent, zero-mean, and of dimensions d_r × d_c.
F Ahlswede-Winter matrix bound: The same bound also applies when each matrix is sub-exponential with parameter M = ||Y^(i)||_ψ1.The Orlicz norm uses ψ1(x) = exp(x) − 1, appropriate for sub-exponential variables.