Source-linked AI summary
Low-rank Matrix Recovery from Errors and Erasures
Yudong Chen, Ali Jalali, Sujay Sanghavi, Constantine Caramanis
TL;DR
The paper asks when a low-rank matrix can be exactly recovered from partial observations containing unknown, arbitrary corruptions. It analyzes a convex nuclear-norm-plus-ℓ1 relaxation and proves unified guarantees covering mixed random and deterministic patterns, vanishing observation fractions, and deterministic matrix completion.
Problem
The problem is to recover a low-rank matrix and observed sparse errors when most entries are erased and unknown observed entries may be grossly corrupted.
Method
The paper uses a convex nuclear-norm-plus-ℓ1 program and constructs a minimum-norm dual certificate to certify exact recovery.
Results
The unified guarantees cover simultaneous random and deterministic errors and erasures, including vanishing observation fractions and deterministic matrix completion.
Takeaways & Limitations
The results extend existing matrix-completion and sparse/low-rank-recovery guarantees while addressing corrupted matrices with very few observations.
Abstract
from arXiv · showhide
This paper considers the recovery of a low-rank matrix from an observed version that simultaneously contains both (a) erasures: most entries are not observed, and (b) errors: values at a constant fraction of (unknown) locations are arbitrarily corrupted. We provide a new unified performance guarantee on when the natural convex relaxation of minimizing rank plus support succeeds in exact recovery. Our result allows for the simultaneous presence of random and deterministic components in both the error and erasure patterns. On the one hand, corollaries obtained by specializing this one single result in different ways recover (up to poly-log factors) all the existing works in matrix completion, and sparse and low-rank matrix recovery. On the other hand, our results also provide the first guarantees for (a) recovery when we observe a vanishing fraction of entries of a corrupted matrix, and (b) deterministic matrix completion.
I. INTRODUCTION
The paper studies exact recovery of low-rank matrices when observations contain both erasures and malicious errors, using a convex rank-plus-support relaxation. Its unified guarantees cover mixed random and deterministic patterns, vanishing observation rates, and deterministic matrix completion.
- Vanishing observations: Exact recovery is guaranteed with as few as Θ(npolylog(n)) observed entries even when a constant fraction of those entries are errors.This is the paper’s vanishing-observation regime for random support patterns.
- Random-sign errors: Theorem 2 permits recovery when almost all entries are corrupted under symmetric random error signs, including a vanishing fraction of observations.The random-sign assumption applies to errors in the random component outside the deterministic error support.
- Deterministic patterns: Theorem 3 gives the first guarantees for simultaneous deterministic errors and erasures, including deterministic matrix completion under potentially adversarial erasures.Its errors-only specialization improves the order over prior deterministic results and matches another result’s scaling with a simpler proof.
- Problem: The recovery problem combines mostly unobserved entries with gross corruption at unknown locations among observed entries.The target is the underlying low-rank matrix, together with the observed entries of the sparse error matrix.
- Method: The convex program minimizes the nuclear norm of the low-rank component plus a weighted elementwise ℓ1 norm of the error component.The nuclear norm substitutes for rank, the ℓ1 norm substitutes for sparsity, and γ trades off the two terms.
- Unified guarantee: The unified guarantee handles simultaneous random and adversarial patterns in both errors and erasures, recovering existing matrix-recovery results up to constants or logarithmic factors.The model represents observations as the intersection of random and deterministic observed sets, and errors as the union of random and deterministic supports.
C. Improved Guarantee for Errors with Random Sign
With random signs on errors, the paper proves recovery despite an overwhelming fraction of corruptions and a vanishing fraction of observations. The deterministic guarantee further establishes recovery under arbitrary error and erasure patterns subject to spread conditions.
- C. Improved Guarantee for Errors with Random Sign: Random error signs permit exact recovery even when almost all entries are corrupted.Theorem 2 assumes symmetric ±1 signs for random errors and extends prior guarantees to a vanishing fraction of observations.
- C. Improved Guarantee for Errors with Random Sign: p0 can approach zero faster than 1 −τ because known erasure locations are easier to correct than unknown error locations.
- D. Improved Deterministic Guarantee: The deterministic analysis requires at most d errors and erasures per row or column and a spectral-to-entrywise norm bound with parameter ηd.
- D. Improved Deterministic Guarantee: Theorem 3 guarantees unique exact recovery under arbitrary errors and erasures satisfying these spread conditions.
- D. Improved Deterministic Guarantee: The deterministic bound improves prior scaling from d^2r to dr for square matrices while retaining comparable scaling to recent work.
- D. Improved Deterministic Guarantee: The proofs certify optimality through a dual matrix Q for the convex program, despite dense errors, erasures, and mixed deterministic-random components.
A. Step 1: Sign Pattern Derandomization
The proof removes the random-sign restriction through derandomization and then establishes invertibility and dual-certificate conditions for the convex program. These steps reduce arbitrary signed errors to the random-sign analysis while handling mixed support patterns.
- A. Step 1: Sign Pattern Derandomization: Theorem 1 follows from Theorem 2 by a derandomization and elimination argument for arbitrary error signs.
- A. Step 1: Sign Pattern Derandomization: A fixed-sign error matrix can be viewed as a trimmed random-sign matrix, making successful recovery under random signs sufficient for the fixed-sign model.
- A. Step 1: Sign Pattern Derandomization: Exact recovery requires the uncorrupted, un-erased entries to identify matrices in T, which is established by proving PT PΓPT invertible on T.
- A. Step 1: Sign Pattern Derandomization: The invertibility lemma generalizes prior random-entry results by combining random and deterministic components in the observed clean set.
- A. Step 1: Sign Pattern Derandomization: A dual certificate Q proves unique optimality when its projections and norm constraints satisfy the sufficient optimality condition.
D. Step 4: Construction of the Dual Certificate
The dual certificate is constructed by repeatedly correcting and resampling errors across independent batches of observed clean entries. Its validity follows from geometric error contraction plus separate bounds for dependent random-sign terms.
- D. Step 4: Construction of the Dual Certificate: The construction uses a Golfing Scheme variant to approximate UV ⊤−γPT E∗ while satisfying the certificate constraints.
- D. Step 4: Construction of the Dual Certificate: Each correction-and-sampling step reduces the certificate error geometrically fast.
- D. Step 4: Construction of the Dual Certificate: The observed clean set is decomposed into k0=⌈4 log n⌉ independent batches, enabling recursive construction of W from scaled projections.
- D. Step 4: Construction of the Dual Certificate: The step error obeys Dk=(PT−PT RΓ(k)PT)Dk−1, yielding geometric convergence after repeated batch updates.
- D. Step 4: Construction of the Dual Certificate: Dependence between E∗ and the clean-entry batches is handled using conditional independence after conditioning on Ω.
- D. Step 4: Construction of the Dual Certificate: The proof separates Type-1 terms, bounded by concentration, from Type-2 terms, bounded using the random signs of E∗.
IV. PROOF OF THEOREM 3
The proof of Theorem 3 follows the standard dual-certificate roadmap: derive a sufficient optimality condition, construct a certificate, and verify its constraints under deterministic errors and erasures.
- IV. PROOF OF THEOREM 3: The proof first formulates a dual-certificate optimality condition for the convex program.
- IV. PROOF OF THEOREM 3: It then constructs a candidate certificate and proves that the candidate certifies the optimum.
1) Optimality conditions:
Lemma 5 gives first-order conditions for unique optimality: sparse and low-rank components must be distinguishable, and a dual matrix must satisfy projection equalities and strict inequalities.
- Optimality condition: The pair (PΦ(A∗), B∗) is uniquely optimal when Γc ∩ T = {0} and a suitable dual matrix Q exists.The dual matrix must satisfy PΦc(Q) = 0 together with the conditions in (20).
- Optimality condition: Condition Γc ∩ T = {0} prevents any nonzero matrix from being both sparse and low-rank.This distinguishes the sparse and low-rank components without ambiguity.
- Identifiability: α < 1 is sufficient to guarantee Γc ∩ T = {0}.The proof bounds the relevant projection so that any matrix in the intersection must be zero.
2) Dual Certificate:
The paper constructs the dual certificate as Q = Qa + Qb, using convergent series that separately enforce the sparse-error and low-rank components of the optimality conditions.
- Construction: Qa and Qb are constructed as candidate dual-certificate components, with M∗ = γ sgn(A∗) and N∗ = UV⊤.The construction differs from earlier dual-certificate methods and uses a minimum-norm solution to the equality constraints.
- Convergence: Qa and Qb are well-defined when α < 1 because their defining infinite sums converge.The convergence follows from geometric contraction of the projection operator.
- Verification: Q = Qa + Qb satisfies the equality conditions and PΦc(Q) = 0; the remaining inequalities are verified separately.Equation (22) supplies the componentwise projection identities used in this step.
SPT (M∗)
The analysis bounds the candidate certificate using geometric convergence and incoherence, while simulations test how recovery thresholds change with matrix size under random and deterministic corruption.
- SPT (M∗): The series operator satisfies ∥SW∥∞ ≤ 1/(1−α) ∥W∥∞ because its projection terms converge geometrically.This bound supports control of the candidate dual certificate.
- SPT (M∗): Incoherence assumptions and orthonormality of U and V control the complementary projections needed for the dual-certificate inequalities.The analysis uses bounds such as ∥I − UU⊤∥ ≤ 1 and ∥I − VV⊤∥ ≤ 1.
- Experiments: The simulations report that recovery conditions become increasingly relaxed as n increases.The experiments examine minimum observation probability, maximum tolerable corruption probability, and maximum tolerable deterministic noise.
- Experiments: Higher corruption probabilities are tolerated as matrix size increases when p0 = 0.9 and d = 0.This experiment uses rank-two matrices and tracks the phase transition in τ.
- Experiments: The tolerable adversarial block size d grows linearly with n when p0 = 0.5 and τ = 0.1.The adversarial noise is a diagonal d × d block of ones, creating a concentrated corruption pattern.
APPENDIX
The appendix develops concentration and projection bounds for random and deterministic index sets, supporting the unified recovery guarantees through operator-norm and infinity-norm control.
- Technical tools: Non-commutative Bernstein inequalities bound random operator deviations formed from independent, bounded, zero-mean matrix variables.This is the main concentration tool used in several technical lemmas.
- Final estimates: The proof begins with deterministic-set control and represents tangent-space matrices as Z = UX⊤ + U⊥YV⊤.This representation enables the final norm estimates using incoherence and projection properties.
- Projection bounds: For Bernoulli-observed indices and a fixed index set, Lemma 11 controls deviations of projected operators with high probability.The deterministic-set specialization applies when the fixed set is Γd under Theorem 2 assumptions.
- Error bounds: Under Theorem 2 assumptions, deterministic corruption sets are controlled using row- and column-sparsity bounds, while random signed entries are handled probabilistically.The random-sign argument applies Bernstein inequalities and union bounds to bound projected error terms.
- Final estimates: The appendix combines diagonal and off-diagonal operator-norm estimates with incoherence-based bounds to complete the required technical lemmas.These estimates control terms involving random sampling, deterministic sets, and the error matrix.