Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization

I. INTRODUCTION

• Joint low-rank and sparse minimization covers applications including face recognition, collaborative filtering, background modeling, subspace segmentation, matrix completion, RPCA, and LRR.The paper frames these as instances of a general optimization problem.Source: §I · p. 1
• For lower-rank or sparser solutions, the paper also considers the nonconvex Schatten-p norm with 0 < p < 1.Source: §I · p. 1

A. Related Works

• Earlier solvers face trade-offs: SDP scales as O(n^6), APG requires a Lipschitz-continuous gradient, and ADM variants can incur auxiliary-variable or convergence issues.Partial SVD may also be no faster than full SVD when the solution rank is not sufficiently low.Source: A. Related Works · pp. 1–2
• Prior IRLS methods handled only a single ℓ1 or nuclear-norm term with squared loss or an affine constraint, motivating a broader method for multiple non-smooth terms.The paper aims to avoid auxiliary variables and SVD computation.Source: A. Related Works · p. 2

B. Contributions

• The proposed method smooths the low-rank and sparse objective terms, then applies IRLS to solve the relaxed problem.The paper presents this as a general approach to the joint minimization problem.Source: B. Contributions · p. 2
• For the Schatten-p and ℓ2,q-regularized LRR example, IRLS yields a stationary point and a globally optimal point when p, q ≥ 1.Source: B. Contributions · p. 2
• The contribution summary reports that IRLS is more efficient than state-of-the-art ADM-family algorithms because it avoids SVD computation.Source: B. Contributions · p. 2

II. SMOOTHED LOW RANK REPRESENTATION

• LRR is chosen as a representative example because it combines low-rank and column-sparse minimization and has applications in machine learning and computer vision.Source: §II · p. 2
• The smoothed LRR objective uses regularization terms to make both non-smooth terms smooth, and it is convex when p, q ≥ 1.In that regime, the paper states that the smoothed problem has a globally optimal solution.Source: §II · p. 2
• The smoothed objective majorizes the original objective, and decreasing it tends to decrease the original objective as well.The paper also states that for any ϵ > 0, a µ exists with J(Z, µ) ≤ J(Z) + ϵ.Source: §II · p. 2

III. IRLS ALGORITHM

• With fixed weight matrices, the representation update solves a Sylvester equation; a general solver costs O(n^3).When X^T X has certain structure, the cost may be O(n^2).Source: §III · p. 3
• IRLS alternates between updating Z and weights M and N, which correspond respectively to the low-rank and sparse terms.The weights are computed from Z, while fixed weights allow solving for Z.Source: §III · p. 3
• IRLS has O(n^3) per-iteration complexity and avoids SVD, but accelerated LADMAP may be faster when the rank of Z is sufficiently low.The paper reports that IRLS outperforms accelerated LADMAP on several real applications, while noting its convergence rate is not established.Source: §III · p. 3
• The same smoothing-and-reweighting approach can extend beyond LRR to structured Lasso variants, robust matrix completion, and RPCA.The paper describes the broader procedure as smoothing the objective, expressing derivatives through weights, and alternately updating the variable and weights.Source: §III · p. 3

IV. ALGORITHMIC ANALYSIS

• The analysis generalizes IRLS to minimizing two or more non-smooth terms, with proofs that do not rely on a squared-loss term.The authors describe their convergence analysis as general despite deriving it for the LRR algorithm.Source: §IV · p. 3
• Theorem 2 states that J(Zt, µ) is non-increasing, the iterates are bounded, and successive iterates become arbitrarily close.The reported limit is ||Zt − Zt+1||F → 0.Source: §IV · p. 4
• Theorem 3 establishes that every limit point is stationary for problem (6), and globally optimal when p, q ≥ 1.Source: §IV · p. 4
• The proof uses concavity and also applies to other concave functions, including log(x), beyond the specific norm functions discussed.Table I is described as listing popular norms, their smoothed versions, and derivatives for 0 < p < 2.Source: §IV · p. 4, Table I · p. 4

V. EXPERIMENTS

• Experiments evaluate IRLS on synthetic and real data for both LRR and IRPCA.Source: §V · p. 4
• For comparison with previous convex LRR solvers, the experiments set p = q = 1 in problem (5).Source: §V · p. 4
• The evaluation examines IRLS sensitivity to µ before comparing its performance with state-of-the-art methods.Source: §V · p. 4

A. Selection of Regularization Parameter µ

• The method decreases µ by µt+1 = µt/ρ, with ρ > 1, and initializes µ0 as µc times the spectral norm of X.The authors report fast convergence and accurate solutions when µ is chosen appropriately.Source: A. Selection of Regularization… · p. 4
• µc = 0.1 and ρ = 1.1 work well; smaller µc or larger ρ can reduce accuracy, while larger µc or smaller ρ delays convergence.The convergence curves compare µc with ρ fixed at 1.1 and ρ with µc fixed at 0.1.Source: Figure 1 · p. 5, A. Selection of Regularization… · p. 5
• The sensitivity experiments use synthetic data, varying µc with ρ fixed and then varying ρ with µc fixed.The figure fixes ρ = 1.1 for the µc comparison and µc = 0.1 for the ρ comparison.Source: A. Selection of Regularization… · p. 5, Figure 1 · p. 5

B. LRR for Subspace Segmentation

• The LRR comparisons use IRLS with μ0 = 0.1||X||2 and ρ = 1.1; LADMAP(A) is allowed up to 10000 iterations.Other methods use their released-code default parameters; ADM-type methods use PROPACK for SVD.Source: B. LRR for Subspace Segmentation · p. 5

1) Synthetic Data Example

• IRLS is faster than APG, ADM, and LADM on synthetic data, and outperforms LADMAP and LADMAP(A) except when λ = 0.1.For small-sized or high-rank problems, IRLS is a better choice than LADMAP(A) because it avoids SVD.Source: 1) Synthetic Data Example · pp. 5–6

2) Face Clustering

• IRLS is the fastest and most accurate method for face clustering on the 5- and 10-subject Extended Yale B subsets.The linearized methods do not converge within 1000 iterations.Source: 2) Face Clustering · p. 6, Figure 4 · p. 6, Table III · p. 6

3) Motion Segmentation

• IRLS is the fastest method for Hopkins 155 motion segmentation, while LADMAP(A) is competitive but requires many more iterations.The database sequences contain two or three motions, with 39 to 550 data points each.Source: 3) Motion Segmentation · p. 6

C. Inductive Robust Principal Component Analysis

• The model uses the ℓ1,2-norm, the sum of row-wise ℓ2 norms, to handle row corruptions such as shadows from glasses or scarves.This replaces the ℓ1-norm used in the cited IRPCA formulation.Source: C. Inductive Robust Principal… · p. 6
• The IRPCA experiments learn a projection from training faces and apply it to test data; evaluation uses Extended Yale B and the C07 near-frontal pose of CMU PIE.Extended Yale B uses 30 training images per subject; C07 uses 10 training images per subject, with SVM classification.Source: C. Inductive Robust Principal… · pp. 6–7
• Recognition accuracies are almost the same across solvers, but ADM and LADMAP(A) take much longer than IRLS; IRPCA by IRLS removes facial shadows and corruptions.Figure 5 compares accuracy and running time, while Figure 6 shows recovered test faces.Source: C. Inductive Robust Principal… · p. 7, Figure 5 · p. 7, Figure 6 · p. 7

VI. CONCLUSIONS AND FUTURE WORK

• The paper generalizes IRLS to joint low-rank and sparse minimization, proving its solution is stationary and globally optimal when the problem is convex.It identifies nonconvex structured Lasso as future work.Source: §VI · p. 7

A. Proof of Lemma 1

• The proof of Lemma 1 begins by applying the definition of a concave function.Source: A. Proof of Lemma 1 · p. 7
• The proof invokes an inequality relating Tr(X^T Y^(p−1)) to products of ordered eigenvalues of X and Y.The passage states that the eigenvalues are ordered from largest to smallest.Source: A. Proof of Lemma 1 · p. 7

B. Proof of Lemma 2

• For 0 < p < 1, concavity of x^p is used to conclude that Tr(X^p) is concave.This is the stated conclusion of the proof of Lemma 2.Source: B. Proof of Lemma 2 · p. 8

• The proof tracks E_t = XZ_t − X to relate the residual change to the weighted update.Source: C. Proof of Theorem 2 · p. 8
• J(Z_t, μ) is non-increasing across iterations.Source: C. Proof of Theorem 2 · p. 8
• The iterate sequence {Z_t} is bounded; the proof also states bounds on the minimum eigenvalues of M_t and N_t.Source: C. Proof of Theorem 2 · p. 8

• When p, q ≥ 1, problem (6) is convex, so a stationary point is globally optimal.Source: D. Proof of Theorem 3 · p. 8
• Boundedness of {Z_t} ensures a convergent subsequence with a matrix limit.Source: D. Proof of Theorem 3 · p. 8
• The limit Z* satisfies problem (6)'s first-order optimality condition.Source: D. Proof of Theorem 3 · p. 8