Robust Matrix Completion

1 Introduction

• The paper studies noisy recovery of a low-rank matrix from partial observations of its sum with a matrix having entrywise or columnwise sparsity.Corrupted entries are not identified for the observer.Source: §1 · p. 2
• The observed indices are divided into non-corrupted and corrupted sets, but the observer does not know which set contains a given observation.The two sets have non-random sizes.Source: §1 · pp. 2–3
• The authors present this as the first study of noisy robust matrix completion and do not require incoherence, known rank, or a known sparsity level.They explain that these weaker assumptions are compatible with targeting approximate rather than exact recovery.Source: §1 · p. 3
• The approach allows general, unknown sampling distributions and requires only an upper bound on the absolute entry magnitudes of the low-rank and sparse components.The paper notes that such a bound may be available as a maximum rating in recommendation systems.Source: §1 · pp. 3–4
• When corrupted columns and the corrupted-observation share are small, O(r max(m1,m2)) observations suffice, and rates for both corruption structures are minimax optimal up to logarithmic factors.The sample-count implication is stated for columnwise corruption; minimax optimality applies to both columnwise and entrywise corruption.Source: §1 · p. 4

2.1 Notation and definitions

• The index sets distinguish corruption locations for columnwise and entrywise sparsity, while the corruption penalty uses a norm and its associated dual norm.Source: §2.1 · p. 5

2.2 Convex relaxation for robust matrix completion

• The estimator combines a nuclear-norm penalty with a corruption penalty chosen for the structure of S0, using the 2,1 norm for columnwise sparsity and the l1 norm for entrywise sparsity.The stated formulation uses a shared upper bound a on the entry magnitudes of L0 and S0, with the text noting that separate bounds can also be accommodated.Source: §2.2 · p. 6

2.3 Assumptions on the sampling scheme and on the noise

• Non-corrupted observations are i.i.d. draws under a sampling distribution, while the sampling of corrupted observations is unrestricted; the noise is assumed sub-Gaussian.The sampling assumptions also restrict how heavily any row or column is sampled.Source: §2.3 · pp. 7–8

• The general result is then applied to entrywise-sparse and columnwise-sparse corruption settings using l1 and 2,1 regularizers, respectively.Source: §3 · p. 8
• The bound’s Ψ1 term represents rank-r matrix-completion error, while its second and third terms account for corruption-induced error.Source: §3 · p. 9

4 Columnwise sparse corruptions

• The columnwise-sparse setting assumes S0 has at most s nonzero columns, with s ≤ m2/2, and uses the ℓ2,1-norm regularizer.The resulting convex program is the columnwise specialization of the paper's general estimator.Source: §4 · p. 9
• The sampling condition prevents columns from being sampled too often and ensures non-corrupted observations are well spread across columns.The paper notes that approximately uniform sampling satisfies this condition.Source: §4 · p. 10
• The prediction-error bound has a usual matrix-completion term proportional to rM/n and corruption terms proportional to the number of corrupted columns s and corrupted observations |˜Ω|.The corruption contribution vanishes when S0 = 0.Source: §4 · p. 12
• When s ≪ m2, the stated sufficient condition on non-corrupted observations n yields small prediction error and can require fewer than m1m2 observations when r is small.The condition is expressed using |˜Ω|, the number of corrupted observations.Source: §4 · p. 12

5 Entrywise sparse corruptions

• The setting allows S0 to have at most s nonzero entries, not necessarily concentrated in a small set of columns, and uses the ℓ1 regularizer.Source: §5 · pp. 12–13
• The sampling assumption prevents any entry from being sampled too often and ensures observations are well spread over non-corrupted entries.Together with the stated assumptions, it makes the sampling distribution approximately uniform.Source: §5 · p. 13
• The prediction-error bound contains the usual matrix-completion term proportional to rM/n and corruption terms proportional to the number s of nonzero entries and corrupted observations |˜Ω|.The paper states these error terms are of the correct order up to a logarithmic factor.Source: §5 · p. 15
• When s ≪ n < m1m2, the bound implies estimation from a nearly minimal number of observations despite corruption of some observations.Source: §5 · p. 15

6 Minimax lower bounds

• The section's stated aim is to show that the estimator's rates are optimal up to a logarithmic factor by proving minimax lower bounds.Source: §6 · p. 15
• Theorem 2 assumes m1,m2≥2, 1≤r≤min(m1,m2), 1≤s≤m2/2, Assumption 9, Mr≤n, |˜Ω|≤sm1, æ≤1+s/m2, and i.i.d. Gaussian noise N(0, σ2) with σ2>0.Source: §6 · p. 15
• Theorem 3 assumes m1,m2≥2, 1≤r≤min(m1,m2), 1≤s≤m1m2/2, Assumption 9, Mr≤n, |˜Ω|≤ρrM for ρ>0, and i.i.d. Gaussian ξi∼N(0,σ²) with σ²>0.Source: §6 · p. 16

A.1 Proof of Theorem 1

• Corruptions make the restricted strong convexity proof the main difficulty and require a new approach beyond methods for noisy matrix completion.Source: §A.1 · p. 16
• The analysis seeks to upper-bound the Frobenius-norm estimation error ∥L0 −ˆL∥2, using estimator optimality, F(ˆL, ˆS) ≤ F(L0, S0), as part of its argument.Source: §A.1 · p. 16
• The sampling operator is shown to capture a substantial component of pairs of low-rank and sparse matrices in a constrained set, yielding the needed restricted strong convexity control.Source: §A.1 · p. 18

B Proof of Theorems 2 and 3

• The constructed class and pairwise differences have rank at most r and at most s nonzero sparse columns, with entries in [0, a].These properties ensure the class lies in A_GS(r, s, a).Source: B Proof of Theorems 2 and 3 · p. 30
• A packing restricted to S = 0 establishes a lower bound of order rM/n for the low-rank component.The Varshamov-Gilbert construction supplies a subset containing zero with cardinality at least 2^(rM/8) + 1.Source: B Proof of Theorems 2 and 3 · p. 30
• A separate packing restricted to L = 0 supplies a lower-bound argument for the corruption component.The construction uses a Varshamov-Gilbert subset containing zero, with cardinality at least 2^(sm1/8) + 1.Source: B Proof of Theorems 2 and 3 · p. 30
• Theorem 2 follows by combining inequalities (55), (59), and (61).The proof establishes these inequalities for the lower-bound argument.Source: B Proof of Theorems 2 and 3 · p. 31
• Theorem 3 follows the same proof lines as Theorem 2, with the sparse set replaced by a modified construction.The section omits the remaining proof details.Source: B Proof of Theorems 2 and 3 · p. 31

C Proof of Lemma 6

• A Hanson–Wright inequality is applied after conditioning on the sampling variables to obtain a probability bound.The proof then combines this bound with an earlier inequality to control the target quantity.Source: C Proof of Lemma 6 · pp. 31–32
• A coordinate-count term is treated as binomial and bounded with Bernstein’s inequality, followed by a union bound over matrix coordinates.The proof assumes log m2 ≥ 1 for one stated probability bound.Source: C Proof of Lemma 6 · pp. 32–33
• A random variable in the proof is identified as an order-2 U-statistic and controlled with a Bernstein-type concentration inequality.The argument introduces independent replications and evaluates the associated quantities for the sampling setup.Source: C Proof of Lemma 6 · pp. 33–34
• The proof applies a decoupling argument and a concentration result from to bound the U-statistic term.The resulting bounds are combined with bounds on A, B, C, and D.Source: C Proof of Lemma 6 · pp. 35–36

D Proof of Lemma 10

• Subgaussian noise and Bernstein’s inequality yield coordinatewise bounds, extended across entries by a union bound.The proof uses these bounds to obtain the stated controls on Σ and ΣR.Source: D Proof of Lemma 10 · p. 37

E Technical Lemmas

• The technical lemmas provide a tail-based bound for a nonnegative random variable and an inequality for the dual of an absolute norm.The latter argument uses ⟨Xi, ∆L⟩ ≤ ∥∆L∥∞ ≤ 2a.Source: E Technical Lemmas · pp. 37–38