PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Rank Structure Learning via Log-Sum Heuristic Recovery

Yue Deng, Qionghai Dai, Risheng Liu, Zengke Zhang, Sanqing Hu

arXiv:1012.1919v3math.NAcs.ITcs.LGcs.NAmath.IT

TL;DR

Recovering low-rank structure from corrupted data is difficult when ℓ1 heuristics face high-rank structure or dense errors. The paper proposes LHR, which uses log-sum sparsity with an MM solver, and reports an expanded RPCA feasible region alongside results on subspace clustering.

  • Problem

    Low-rank structure learning seeks to recover low-rank data and sparse errors from corrupted observations, while ℓ1 heuristics may underperform for high-rank structure or dense corruptions.

    Source: §I · p. 1

  • Method

    LHR uses a log-sum sparsity term and an MM algorithm that replaces its non-convex objective with convex surrogates.

    Source: §I · p. 1, C. The majorization-minimization for… · p. 4

  • Results

    LHR extends the PCP feasible boundary to η_LHR + ξ_LHR = 0.58 and is reported to achieve state-of-the-art results on motion segmentation and promising results on stock clustering.

    Source: §I · p. 2, §VI · p. 11

  • Takeaways & Limitations

    The paper applies LHR as a general low-rank structure learning approach to matrix recovery and subspace clustering, including stock clustering.

    Source: §I · p. 2, §VI · p. 11

    Because LHR is non-convex, convergence to a stationary point does not establish a global minimum; the paper uses an ℓ1 solution as its starting point.

    Source: D. Theoretical justifications · p. 5

Abstract

from arXiv · show

Recovering intrinsic data structure from corrupted observations plays an important role in various tasks in the communities of machine learning and signal processing. In this paper, we propose a novel model, named log-sum heuristic recovery (LHR), to learn the essential low-rank structure from corrupted data. Different from traditional approaches, which directly utilize $\ell_1$ norm to measure the sparseness, LHR introduces a more reasonable log-sum measurement to enhance the sparsity in both the intrinsic low-rank structure and in the sparse corruptions. Although the proposed LHR optimization is no longer convex, it still can be effectively solved by a majorization-minimization (MM) type algorithm, with which the non-convex objective function is iteratively replaced by its convex surrogate and LHR finally falls into the general framework of reweighed approaches. We prove that the MM-type algorithm can converge to a stationary point after successive iteration. We test the performance of our proposed model by applying it to solve two typical problems: robust principal component analysis (RPCA) and low-rank representation (LRR). For RPCA, we compare LHR with the benchmark Principal Component Pursuit (PCP) method from both the perspectives of simulations and practical applications. For LRR, we apply LHR to compute the low-rank representation matrix for motion segmentation and stock clustering. Experimental results on low rank structure learning demonstrate that the proposed Log-sum based model performs much better than the $\ell_1$-based method on for data with higher rank and with denser corruptions.

I. INTRODUCTION

The paper introduces LHR for learning low-rank structure from corrupted data, targeting cases where ℓ1-based approaches may struggle, such as high-rank structure or dense errors. It positions LHR across matrix recovery and subspace clustering, and describes an MM solver for its non-convex objective.

I. INTRODUCTION

  • The paper frames low-rank structure learning as recovering low-rank data and sparse errors from corrupted observations, an ill-posed problem addressed through optimization.The formulation is presented as relevant to machine learning and signal processing.Source: §I · p. 1
  • The authors argue that convex ℓ1 heuristics may underperform when the desired matrix has high intrinsic rank or corruptions are dense.They motivate non-convex approximation as a way to enhance signal sparsity in these harder cases.Source: §I · p. 1
  • LHR extends the PCP feasible boundary from η_PCP + ξ_PCP = 0.35 to η_LHR + ξ_LHR = 0.58 in simulations.The paper also reports applications to shadow removal and video background modeling.Source: §I · p. 2

2) Low rank representation:

  • For low-rank representation, the paper applies LHR to subspace clustering and reports higher clustering accuracy than other state-of-the-art algorithms in motion segmentation and stock clustering.The improvements are especially noticeable on stock data with significant disturbances.Source: §I · p. 2

I. INTRODUCTION

  • LHR uses a log-sum sparsity term and an MM algorithm that replaces the non-convex objective with convex surrogates; the authors prove convergence to a stationary point.The paper describes the resulting approach as a reweighted scheme.Source: §I · pp. 1–2

B. MM algorithm and reweighted approaches

  • The related-work discussion distinguishes this approach by addressing low-rank structure learning from corruptions and using ADM-style first-order optimization to extend learning to large-scale matrices.Prior reweighted nuclear-norm approaches cited here use semidefinite programming and are described as limited to relatively small matrices.Source: B. MM algorithm and reweighted… · p. 3

III. CORRUPTED MATRIX RECOVERY VIA LOG-SUM

This section contrasts the convex ℓ1 heuristic with LHR’s log-sum sparsity penalty for corrupted matrix recovery. The log-sum term is presented as a closer approximation to ℓ0 sparsity, while its non-convexity motivates an MM solution.

A. ℓ1 heuristic for corrupted low rank matrix recovery

  • The ℓ1 heuristic replaces matrix rank with the nuclear norm and sparse errors with the ℓ1 norm, yielding a convex alternative to the intractable rank-plus-ℓ0 formulation.The paper recasts the nuclear norm through auxiliary positive-definite matrices, expressing the resulting optimization in terms of ℓ1 norms.Source: A. ℓ1 heuristic for corrupted low rank… · p. 3

B. Log-sum heuristic for matrix recovery

C. The majorization-minimization for LHR optimization

The MM procedure makes LHR tractable by iteratively constructing and minimizing convex upper bounds for its non-convex objective. The section describes Taylor expansion as a way to form those bounds.

C. The majorization-minimization for LHR optimization

D. Theoretical justifications

The MM framework monotonically decreases LHR’s non-convex objective and its iterates converge to a stationary point. This convergence does not establish a global minimum; the paper uses the ℓ1 solution as a starting point for a satisfactory result.

D. Theoretical justifications

  • MM monotonically decreases the non-convex objective by minimizing a convex upper-bound that touches the objective at the current iterate.The surrogate upper-bounds the objective, and minimizing it yields the descent step.Source: D. Theoretical justifications · p. 4
  • The MM-generated sequence converges to a limit point, and the LHR limit is a stationary point of its objective.The proof uses the surrogate’s tangency to the objective at a fixed point to establish stationarity.Source: D. Theoretical justifications · p. 5
  • Convergence to a stationary point does not guarantee a global minimum because LHR’s objective is non-convex.The paper initializes with the ℓ1 heuristic solution, which it says can lead to a satisfactory result.Source: D. Theoretical justifications · p. 5

E. Solve LHR via reweighted approaches

LHR is solved by iteratively replacing its non-convex objective with convex surrogates, producing a sequence of reweighted convex problems. The resulting convex objective combines a nuclear norm and an ℓ1 norm.

E. Solve LHR via reweighted approaches

IV. LOW RANK MATRIX RECOVERY FROM CORRUPTIONS

The paper adapts LHR to recover low-rank matrices from sparse corruptions and compares it with PCP. Its joint optimization uses alternating updates for the corruption, auxiliary nuclear-norm variable, low-rank matrix, and dual variables.

IV. LOW RANK MATRIX RECOVERY FROM CORRUPTIONS

  • LHR is applied to low-rank matrix recovery from corruptions, with performance compared against Principal Component Pursuit (PCP).Source: §IV · p. 6

A. Joint optimization for LHR

  • The joint optimization introduces an auxiliary variable J so the weighted nuclear-norm problem has a closed-form update for its nuclear-norm term.The formulation also uses an equality constraint and an ADM-based solution strategy.Source: A. Joint optimization for LHR · p. 6
  • ADM minimizes the joint objective through E-, J-, and A-minimization steps followed by dual ascent.The method uses Lagrange multipliers for the constraints and updates them by dual ascent.Source: A. Joint optimization for LHR · p. 6
  • The closed-form solution for the auxiliary matrix update is derived from the singular value decomposition of D.Source: A. Joint optimization for LHR · p. 6

B. Numerical simulations

The supplied simulation-section passages identify an evaluation of robust PCA and LHR for low-rank matrix recovery, but do not provide simulation outcomes or numerical comparisons.

B. Numerical simulations

  • The section describes experiments comparing LHR with robust PCP across simulations and practical data, without reporting outcomes in the supplied passages.Source: B. Numerical simulations · p. 6
  • Table I is identified as an evaluation of robust PCA and LHR for low-rank matrix recovery, but its caption supplies no result values.Source: Table I · p. 7
  • The described recovery algorithm initializes the error matrix and iteratively updates variables and dual terms until convergence, then outputs A and E.Source: B. Numerical simulations · p. 7

1) General evaluation:

LHR has a larger feasible recovery region than PCP, including in settings with higher rank and denser errors. The evaluation uses randomly generated matrices and varies rank and corruption rates to compare the methods.

1) General evaluation:

  • The evaluation uses randomly generated squared matrices, with ground-truth low-rank matrices generated by an independent random orthogonal model and sparse errors sampled uniformly with values in [-100,100].Experiments set η + ξ = 0.5; each is repeated ten times, and median values are reported.Source: 1) General evaluation · p. 7
  • In the tested cases, LHR exactly recovers matrices with higher ranks and denser errors than PCP.The authors caution that the table reports only two discrete tests.Source: 1) General evaluation · p. 7

2) Feasible region:

  • LHR’s feasible region extends to roughly η + ξ = 0.575, compared with PCP’s η + ξ = 0.35 boundary.The authors report that parts of LHR’s boundary can extend to η + ρ = 0.6.Source: 2) Feasible region · p. 7

3) Convergence discussions:

Across the video evaluations, LHR outperforms MoG and has lower FNR than PCP, though its FPR is slightly worse on highway and seam. The convergence tests and face examples also show LHR’s recovery behavior under increasing corruption and dense shadows or texture.

3) Convergence discussions:

  • LHR’s first iteration takes the most time, while denser errors increase per-iteration cost and later weighted iterations are faster.The first iteration solves a typical PCP problem; subsequent iterations use different weight matrices.Source: 3) Convergence discussions · p. 8
  • With 15% and 30% gross errors, LHR converges in three iterations; with 45%, it converges in four.The convergence criterion is less than 1e-5, and recovery accuracy rises substantially from the first to the second iteration.Source: 3) Convergence discussions · pp. 7–8

1) Shadow and specularities removal from faces:

2) Video surveillance:

  • For video background modeling, LHR recovers more complete foreground objects and keeps dense corruptions in the sparse-error term.The evaluation uses three benchmark sequences; LHR is described as more robust than PCP to local illumination variations.Source: Figure 3 · p. 9, 2) Video surveillance · p. 9
  • LHR and PCP outperform MoG, while LHR has lower FNR than PCP but slightly higher FPR on highway and seam.The authors suggest moving shadows, labeled as background in the ground truth, may explain the FPR difference.Source: Table II · p. 9, 2) Video surveillance · p. 9

V. LHR FOR LOW RANK REPRESENTATION

The paper applies LHR to low-rank representation, modeling the observed data as P = PA + E, with a low-rank representation matrix and sparse noise. It uses joint optimization and considers motion segmentation and stock clustering as applications.

V. LHR FOR LOW RANK REPRESENTATION

  • For low-rank representation, LHR models the data with P = PA + E, where A is a low-rank correlation-affine matrix and E is sparse noise.The stated applications are motion segmentation and stock clustering.Source: §V · p. 9

A. Joint optimization strategy of LHR for LRR

  • The joint optimization strategy solves a sequence of convex problems, introducing J and equality constraints to make the nuclear-norm term trackable.The paper says it uses an ADM strategy and provides variable-update rules for the resulting optimization.Source: A. Joint optimization strategy of LHR… · p. 9

V. LHR FOR LOW RANK REPRESENTATION

  • The LRR applications include motion segmentation on Hopkins156 and stock clustering, with the latter used to examine performance under substantial corruption.The paper also describes the motion data as slightly corrupted.Source: A. Joint optimization strategy of LHR… · pp. 9–10

B. Motion segmentation in video sequences

The experiments apply subspace clustering to motion segmentation and stock categorization, with LHR performing best among sparse methods and showing larger gains on stock data. The conclusion recommends LHR for higher-rank data and denser corruptions, while noting its greater computational cost.

B. Motion segmentation in video sequences

C. Stock clustering

  • The stock task assigns industrial labels from historical prices, using the assumption that stocks in the same category have similar market performance.The experiments use ten categories in each of the New York and Hong Kong markets.Source: C. Stock clustering · p. 10
  • LHR improves on statistical and graph-based methods by about 20% and on LRR by about 8%, with stock-clustering accuracy of about 63% in the US and 61% in Hong Kong.The table summarizes clustering errors for stocks in ten categories from New York and Hong Kong.Source: Table IV · p. 11, C. Stock clustering · p. 11
  • Stock prices are time-normalized and reduced from 200 dimensions to five by PCA, the dimension at which both markets achieve their maximal clustering accuracies.The data span 200 weekly closing prices from July 2008 to October 2011.Source: C. Stock clustering · p. 11

VI. CONCLUSION

  • The conclusion reports state-of-the-art motion-segmentation results and promising stock-clustering results, and recommends LHR for higher ranks and denser corruptions.The reweighted approach requires repeated convex optimizations and is more time-consuming than PCP and LRR.Source: §VI · p. 11

APPENDIX

The appendix defines abbreviations and supports the convergence argument by establishing boundedness of the iterates and convergence of a subsequence.

A. ABBREVIATIONS

  • The abbreviation list expands the paper's method and algorithm names, including LHR as Log-sum Heuristic Recovery and MM as Majorization Minimization.It also defines LRMR, LRR, LRSL, and the clustering and recovery methods used in the paper.Source: A. ABBREVIATIONS · p. 11

B. Convergence of subsequences in the proof of lemma III.4

  • The iterates are bounded because any variable diverging to infinity would violate the constraints defining the domain, so a convergent subsequence exists.The argument invokes the Bolzano-Weierstrass theorem.Source: B. Convergence of subsequences in the… · p. 12
  • Monotonic decrease of H and the squeeze theorem support convergence of H along the constructed subsequence.The text relates convergence of H on the subsequence to convergence of that subsequence itself.Source: B. Convergence of subsequences in the… · p. 12

Related papers

Loading 1012.1919v3…