PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonconvex Robust Low-rank Matrix Recovery

Xiao Li, Zhihui Zhu, Anthony Man-Cho So, Rene Vidal

arXiv:1809.09237v4cs.ITmath.IT

TL;DR

The paper studies recovery of low-rank matrices from linear measurements corrupted by arbitrary outliers. It uses a factored nonconvex formulation with an ℓ1 loss and shows exact recovery and linear SubGM convergence under stated measurement conditions and suitable initialization.

  • Problem

    The paper addresses recovery of low-rank matrices from linear measurements when an unknown subset of measurements contains arbitrary-magnitude outliers.

    Source: §1.1 · p. 2

  • Method

    The method factors the low-rank matrix variable, uses an ℓ1 measurement-residual loss, and applies a subgradient method to the resulting nonsmooth nonconvex objective.

    Source: §1 · p. 1, §1.1 · pp. 2, 4

  • Results

    With fewer than half the measurements corrupted and ℓ1/ℓ2-RIP for A and A_Ωc, every global minimum recovers X⋆, and suitably initialized SubGM converges linearly.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    Under these conditions, the robust formulation is sharp and weakly convex, so a suitably initialized first-order SubGM has a linear convergence guarantee.

    Source: §1.1 · p. 4

    The theorem's initialization and outlier-fraction requirements are slightly more stringent than the exact-recovery result's; relaxing initialization remains future work.

    Source: §3.5 · p. 16

Abstract

from arXiv · show

In this paper we study the problem of recovering a low-rank matrix from a number of random linear measurements that are corrupted by outliers taking arbitrary values. We consider a nonsmooth nonconvex formulation of the problem, in which we explicitly enforce the low-rank property of the solution by using a factored representation of the matrix variable and employ an $\ell_1$-loss function to robustify the solution against outliers. We show that even when a constant fraction (which can be up to almost half) of the measurements are arbitrarily corrupted, as long as certain measurement operators arising from the measurement model satisfy the so-called $\ell_1/\ell_2$-restricted isometry property, the ground-truth matrix can be exactly recovered from any global minimum of the resulting optimization problem. Furthermore, we show that the objective function of the optimization problem is sharp and weakly convex. Consequently, a subgradient Method (SubGM) with geometrically diminishing step sizes will converge linearly to the ground-truth matrix when suitably initialized. We demonstrate the efficacy of the SubGM for the nonconvex robust low-rank matrix recovery problem with various numerical experiments.

1. Introduction.

The paper addresses robust recovery of low-rank matrices from outlier-corrupted linear measurements with a factored, nonsmooth nonconvex formulation. It gives conditions for exact recovery and linear convergence, then situates these results among existing methods for low-rank recovery and nonsmooth optimization.

1. Introduction.

  • Factored representations can reduce optimization-variable size when the rank is small, addressing a scalability limitation of nuclear-norm methods.The factorization automatically enforces rank and positive-semidefinite constraints in the symmetric positive-semidefinite setting.Source: §1 · pp. 1–2

1.1. Our Goal and Main Results.

  • The formulation combines a factored matrix representation with an ℓ1 loss to address arbitrary-magnitude outliers, whose presence can perturb the ℓ2-loss minima away from X⋆.For general rank-r matrices, the paper uses X = UV^T and a nonsmooth regularizer to address factorization ambiguity.Source: §1.1 · pp. 2, 4
  • With fewer than half the measurements corrupted and ℓ1/ℓ2-RIP for A and A_Ωc, every global minimum recovers X⋆; the objective is sharp and weakly convex, supporting linear convergence of SubGM with suitable initialization.For Gaussian measurements, m ≳ nr is stated to match the information-theoretic measurement bound.Source: §1.1 · pp. 3–4

1.2. Related Work.

  • Compared with prior robust-recovery approaches, the paper states an explicit outlier-fraction bound and requires m ≳ nr measurements, while providing a rigorous justification for SubGM's empirical success.The cited median-truncated gradient method requires m ≳ nr log n measurements, and its maximum tolerated outlier fraction is not explicitly given.Source: §1.2 · p. 5

1.3. Notation.

  • The notation section defines Sign as the subdifferential of absolute value and specifies the matrix and vector norms used in the paper.It also uses ≲ and ≳ for inequalities up to a universal positive constant.Source: §1.3 · p. 5

2. Problem Setup and Preliminaries.

The section introduces sharpness and weak convexity as conditions for analyzing SubGM, then establishes local linear convergence with geometrically diminishing step sizes. Its convergence rate depends on initialization and step-size choices, and the result applies under less restrictive conditions than an earlier guarantee.

2.1. Sharpness and Weak Convexity.

  • Sharpness and weak convexity are the regularity conditions used to establish local linear convergence of SubGM.The theorem assumes these properties with parameters α and τ, respectively.Source: §2.1 · p. 6, §2.2 · p. 7
  • Unlike constant-step SubGM, which can oscillate without converging, geometrically diminishing step sizes can give linear convergence when initialized close to the minimum set.The constant-step example uses h(x) = |x| and oscillates between 0.01 and −0.01.Source: §2.1 · p. 7

2.2. Convergence of SubGM for Sharp Weakly Convex Functions.

  • For sharp, weakly convex functions, geometrically diminishing SubGM step sizes yield linear convergence from an initialization within 2α/τ of the global-minimum set.The iterates satisfy dist(x_k, X) ≤ ρ^k dist_0 under the theorem’s step-size conditions.Source: §2.2 · p. 7
  • Theorem 2 is less restrictive than [15, Corollary 6.1] and still guarantees linear convergence when α/κ = 1.The earlier result’s decay rate approaches one as κ approaches α, so it no longer establishes linear convergence in that case.Source: §2.2 · p. 8
  • As the initialization distance approaches 2α/τ, the allowed initial step size approaches zero and the convergence factor approaches one, so convergence becomes very slow.The initial step size affects both the distance bound and the decay factor.Source: §2.2 · pp. 9–10

3. Nonconvex Robust Low-Rank Matrix Recovery: Symmetric Positive Semidefinite (PSD) Case.

For the PSD case, ℓ1/ℓ2-RIP conditions and an outlier fraction slightly below one-half yield sharpness and exact recovery. Weak convexity then supports linear SubGM convergence with suitable initialization.

3.1. ℓ1/ℓ2-Restricted Isometry Property.

  • For Gaussian sensing with m ≳ nr, A has ℓ1/ℓ2-RIP with high probability on rank-2r matrices; similar RIPs extend the results to other measurement operators.Source: §3.1 · p. 11

3.2. Sharpness and Exact Recovery.

  • With ℓ1/ℓ2-RIP for A and AΩc and the stated outlier bound, every global minimizer recovers X⋆ and the objective is sharp; smaller δ and more measurements permit larger outlier fractions.Source: §3.2 · pp. 12–13

3.3. Weak Convexity.

  • Under ℓ1/ℓ2-RIP for A, the objective is weakly convex, with a parameter independent of the outlier fraction.Source: §3.3 · p. 13

3.4. Putting Everything Together.

  • With the stated initialization and geometrically diminishing steps, SubGM converges linearly to global minimizers whose factors recover X⋆ exactly.The initialization must lie within the theorem's specified neighborhood.Source: §3.4 · p. 15

3.5. Initializing the SubGM.

  • Truncated spectral initialization meets the theorem's proximity requirement under stated Gaussian sample and outlier conditions, which are slightly stricter than the main theorem's; random-start success is empirical.The paper leaves a theoretical justification of random initialization for future work.Source: §3.5 · pp. 15–16
  • For general rank-r matrices, X=UV^T has factorization ambiguity; truncated spectral filtering is proposed to reduce outlier perturbations in PSD initialization.Source: §3.5 · pp. 15–16

4. Nonconvex Robust Low-Rank Matrix Recovery: General Case.

The general case balances the two factors in a rectangular low-rank representation, then establishes exact recovery and objective regularity under restricted-isometry and outlier conditions. These properties support linear convergence of SubGM from a suitable initialization, including one produced by a truncated spectral method under stated conditions.

4. Nonconvex Robust Low-Rank Matrix Recovery: General Case.

  • The general rectangular formulation adds a nonsmooth regularizer to balance U and V, whose product UV^T represents the recovered matrix.The section notes that a similar regularizer used with squared ℓ2-loss is not clearly suitable for the ℓ1 objective because sharpness is then uncertain.Source: §4 · p. 16

4.1. Sharpness and Exact Recovery.

  • Under the outlier bound and ℓ1/ℓ2-RIP conditions, the objective is sharp and its global minimizers correspond exactly to factorizations of the ground-truth matrix.The regularizer removes the additional global minima arising from arbitrary invertible transformations of the factors.Source: §4.1 · pp. 17–18

4.2. Weak Convexity.

  • Under A’s ℓ1/ℓ2-RIP, the objective is weakly convex, including when λ = 0, unlike the sharpness guarantee, which requires λ > 0.The objective’s weak-convexity parameter combines contributions from the loss and the regularizer.Source: §4.2 · pp. 19–20

4.3. Putting Everything Together.

  • With a sufficiently close initialization and prescribed geometrically diminishing step sizes, SubGM converges linearly to a minimizer whose factors recover X⋆.The theorem’s initialization and step-size conditions depend on the sharpness, weak-convexity, and subgradient bounds established in this section.Source: §4.3 · p. 21

4.4. Initializing the SubGM.

  • For Gaussian measurements, truncated spectral initialization is close enough for the convergence theorem with overwhelming probability under the stated sample-size and outlier conditions.The initialization theorem specifies its measurement-count and outlier-fraction conditions.Source: §4.4 · p. 21

5. Experiments.

The experiments show that SubGM recovers matrices across tested outlier levels and, at a high outlier ratio, succeeds where MTGD fails. They also examine geometric and alternative step-size rules, showing linear convergence for several settings while identifying practical or analytical caveats.

Experiments

  • With n = 50, r = 5, and p = 0.3, μ0 = 10 diverged, while μ0 = 1 with ρ ∈ [0.93, 0.99] and μ0 = 0.5 with ρ ∈ [0.95, 0.99] converged to a global minimum.The tested initial step sizes were {0.1, 0.5, 1, 10}; a larger μ0 allowed a smaller decay rate ρ in the reported comparison.Source: §5 · p. 22, Figure 3 · p. 23
  • For μ0 = 1, geometrically diminishing step sizes with ρ larger than 0.93 produced linear convergence, and smaller ρ converged faster.The observed behavior is consistent with the stated O(ρ^k) convergence rate when ρ satisfies the required bound.Source: §5 · p. 22
  • The Polyak step-size rule also showed linear convergence, but generally requires the optimal value f⋆, making it difficult to implement.The rule uses the objective gap divided by the squared subgradient norm.Source: §5 · p. 22
  • Piecewise geometric steps converged piecewise linearly but were generally slightly less efficient, while modified backtracking converged linearly empirically.The authors leave convergence analysis of the backtracking strategy for future work.Source: §5 · pp. 22–23
  • At m = 7nr, SubGM exactly recovered at p = 0.5 while MTGD failed; at low p, both methods succeeded with m = 2nr.Figure 4 varies p from 0 to 0.5 and m/nr from 2 to 7; successful recovery is white and failure black, averaged over 10 trials.Source: §5 · p. 24, Figure 4 · p. 24

6. Conclusion.

The paper presents a factored, ℓ1-loss formulation for robust low-rank recovery and establishes exact recovery under an ℓ1/ℓ2-RIP condition, even with corruption of close to half the measurements. Its objective is sharp and weakly convex, and suitably initialized SubGM converges linearly; random-initialization behavior and possible spurious minima remain open questions.

6. Conclusion.

  • The factored ℓ1-loss formulation exactly recovers the ground-truth matrix from any global minimum under the ℓ1/ℓ2-RIP condition, despite arbitrary corruption of close to half the measurements.The formulation explicitly enforces low rank through factorization and uses the loss to robustify against outliers.Source: §6 · p. 24
  • Sharpness and weak convexity of the objective support linear convergence of geometrically stepped SubGM when suitably initialized.The stated convergence is to the ground-truth matrix.Source: §6 · p. 24
  • Whether the formulation has spurious local minima or random-start SubGM escapes saddle points and converges to a local minimum is left for future work.The numerical experiments suggest efficient recovery with random initialization, but these questions remain unresolved.Source: §6 · p. 25

A.1. Preliminaries.

The preliminaries introduce sub-Gaussian random variables and their norm, a Hoeffding-type inequality, and a covering-net result for low-rank matrices.

A.1. Preliminaries.

  • The preliminaries define sub-Gaussian random variables through equivalent conditions and define their sub-Gaussian norm.The constants in the two conditions differ by at most an absolute constant factor.Source: §A.1 · p. 27
  • A Hoeffding-type inequality is stated for independent, mean-zero sub-Gaussian random variables, using their maximum sub-Gaussian norm and any t > 0.The bound includes an absolute constant.Source: §A.1 · p. 28
  • The low-rank matrix set with unit Frobenius norm and rank at most r admits an ε-net in the Frobenius norm.Source: §A.1 · p. 28

A.2. Isometry Property of a Given Matrix.

For Gaussian measurement matrices, the proof establishes a high-probability bound for a given matrix by centering absolute measurements and applying a Hoeffding-type inequality.

A.2. Isometry Property of a Given Matrix.

  • With i.i.d. standard Gaussian measurement matrices, the lemma establishes a high-probability result for a given matrix.The stated probability exceeds 1 − 2 exp(−c1δ^2m), for a constant c1 > 0 and 0 < δ < 1.Source: §A.2 · p. 28
  • The proof centers each absolute Gaussian measurement and shows the resulting random variable is sub-Gaussian.Source: §A.2 · pp. 28–29
  • Applying the Hoeffding-type inequality to the centered measurements yields the stated bound and completes the proof of (A.4).Source: §A.2 · p. 29

A.3. Proof of Proposition 1.

The proof uses an ε-net and a union bound to establish the desired property on the net, then extends it to all rank-r matrices.

A.3. Proof of Proposition 1.

  • An ε-net argument reduces the proof to unit-Frobenius-norm rank-r matrices, with m ≳ nr sufficient for the stated high-probability result.Source: §A.3 · pp. 29–30
  • A union bound and the given-matrix lemma establish (A.4) for every matrix in the ε-net with high probability.Source: §A.3 · p. 29
  • The proof extends the net result to arbitrary matrices by approximating each with a net point and decomposing the rank-at-most-2r difference into two orthogonal rank-at-most-r matrices.Source: §A.3 · pp. 29–30
  • The extension bounds the approximation error using κr and the net radius ε.Source: §A.3 · p. 30
Loading 1809.09237v4…