Source-linked AI summary
Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
Zhouchen Lin, Risheng Liu, Zhixun Su
TL;DR
Existing LRR solvers based on ADM require costly matrix operations and auxiliary variables that slow convergence, limiting large-scale use. The paper introduces LADMAP, which linearizes the penalty term, adapts the penalty, and accelerates LRR through skinny-SVD techniques; experiments report it is faster than competing methods.
Problem
Existing LRR solvers based on ADM incur O(n^3) computation from matrix multiplications and inversions, while auxiliary variables further slow convergence and hinder large-scale applications.
Method
LADMAP linearizes quadratic penalty terms, adaptively updates the penalty, avoids auxiliary variables and matrix inversions, and uses skinny-SVD and matrix-vector techniques for efficient LRR computation.
Results
Standard and accelerated LADMAP are much faster than APG, ADM, and LADM on the reported real-world experiment, with accelerated LADMAP also faster than standard LADMAP.
Takeaways & Limitations
For LRR, skinny-SVD representations and successive reduced-size matrix operations enable accelerated LADMAP to reduce the computational burden associated with full matrix-matrix multiplications.
Takeaways & Limitations
When ADM subproblems lack closed-form solutions, auxiliary variables and additional constraints are needed, and their least-squares updates often require matrix inversions.
Abstract
from arXiv · showhide
Low-rank representation (LRR) is an effective method for subspace clustering and has found wide applications in computer vision and machine learning. The existing LRR solver is based on the alternating direction method (ADM). It suffers from $O(n^3)$ computation complexity due to the matrix-matrix multiplications and matrix inversions, even if partial SVD is used. Moreover, introducing auxiliary variables also slows down the convergence. Such a heavy computation load prevents LRR from large scale applications. In this paper, we generalize ADM by linearizing the quadratic penalty term and allowing the penalty to change adaptively. We also propose a novel rule to update the penalty such that the convergence is fast. With our linearized ADM with adaptive penalty (LADMAP) method, it is unnecessary to introduce auxiliary variables and invert matrices. The matrix-matrix multiplications are further alleviated by using the skinny SVD representation technique. As a result, we arrive at an algorithm for LRR with complexity $O(rn^2)$, where $r$ is the rank of the representation matrix. Numerical experiments verify that for LRR our LADMAP method is much faster than state-of-the-art algorithms. Although we only present the results on LRR, LADMAP actually can be applied to solving more general convex programs.
1 Introduction
The paper situates LRR and nuclear-norm methods within scalable convex optimization, then addresses computational and convergence limitations of ADM-based LRR solvers with LADMAP.
- Nuclear norm minimization measures 2D sparsity and has been applied to video processing, matrix recovery, unsupervised learning, and semi-supervised learning.
- Interior point methods are unsuitable for large-scale nuclear norm minimization because each iteration has O(n^6) complexity for n × n matrices.
- ADM alternately minimizes the augmented Lagrangian with respect to variables in a Gauss-Seidel manner, while APG offers a guaranteed O(k^-2) convergence rate.
- LRR minimizes the rank of a representation matrix for robust subspace clustering, unlike sparse representation, which minimizes nonzero entries.
- LRR is widely used in computer vision and machine learning applications including motion segmentation, face clustering, and temporal segmentation.
- The existing ADM-based LRR solver has O(n^3) complexity, and auxiliary variables slow convergence by adding variables and constraints.
- LADMAP linearizes the quadratic penalty, adapts the penalty parameter, removes the need for auxiliary variables, and is proved globally convergent for general convex programs.
2 Linearized Alternating Direction Method with Adaptive Penalty
LADMAP linearizes ADM subproblems and adaptively updates the penalty to avoid auxiliary variables while retaining convergence for general convex programs under stated conditions.
- Alternating Direction Method: ADM decomposes the augmented-Lagrangian minimization into alternating x- and y-subproblems because the objective is separable.The augmented Lagrangian includes f(x), g(y), a constraint term, and penalty parameter β.
- Alternating Direction Method: General linear mappings A and B can make ADM subproblems lack closed-form solutions, motivating auxiliary variables, extra constraints, and matrix inversions.These additions also slow convergence.
- Linearized ADM: LADMAP linearizes the quadratic terms in both subproblems and adds proximal terms, avoiding auxiliary variables while enabling efficient updates.The approximation is formed at the current iterate x_k, with analogous treatment for the y-subproblem.
- Adaptive Penalty: The penalty parameter β is updated adaptively because fixed-penalty ADM and LADM can converge slowly and make optimal parameter selection difficult.The proposed rule uses an upper bound β_max and a factor ρ determined by iterate-change conditions.
- Convergence: Under non-decreasing, upper-bounded β_k and η_A > ∥A∥^2, η_B > ∥B∥^2, LADMAP converges to a KKT point of problem (1).The convergence argument uses boundedness and accumulation-point analysis.
3 Applying LADMAP to LRR
LADMAP is specialized to LRR through closed-form shrinkage updates and skinny-SVD-based computation, reducing the accelerated solver's complexity to O(rn^2).
- Applying LADMAP to LRR: LRR is an application of LADMAP because it is a special case of the general convex problem, with closed-form updates for both subproblems.The E update uses l2,1-norm shrinkage and the Z update uses singular-value shrinkage.
- Accelerated Updates: Partial SVD computes leading singular components of the implicit matrix with O(rn^2) complexity, where r is the predicted rank of Z_{k+1}.Because β_k is non-decreasing, the predicted rank is almost non-decreasing across iterations.
- Skinny SVD Acceleration: Representing Z_k by its skinny SVD replaces full matrix multiplications with reduced-size successive multiplications, including the computation of XZ_k.For example, XZ_k becomes ((XU_k)Σ_k)V_k^T.
- Skinny SVD Acceleration: Lanczos matrix-vector products avoid explicitly forming N_k, so partial SVD and the accelerated LADMAP algorithm retain O(rn^2) complexity.The method multiplies vectors successively by N_k's component matrices.
- Computational Cost: Even with partial SVD, the classic LRR ADM solver requires auxiliary variables, matrix multiplications, and inversions, yielding O(n^3) complexity and slow convergence.This computational burden limits large-scale use.
4 Experimental Results
Experiments compare LADMAP variants with APG, ADM, and LADM on synthetic subspaces and Hopkins155 motion data, showing faster computation for LADMAP, especially its accelerated version.
- Synthetic Data: Both standard and accelerated LADMAP require fewer iterations and less CPU time than the other tested methods on synthetic data.The comparison includes APG, ADM, LADM, standard LADMAP, and accelerated LADMAP.
- Synthetic Data: Accelerated LADMAP is substantially faster than standard LADMAP, with a larger advantage when the rank-to-size ratio ˜r/p is smaller.This pattern supports the complexity estimates for the two LADMAP implementations.
- Synthetic Data: ADM and LADM iteration counts appear to increase with problem size, whereas LADMAP iteration counts remain relatively constant.LADM was not allowed to finish on the largest synthetic dataset.
- Synthetic Data: APG produces larger relative errors and lower clustering accuracy than ADM- and LADM-based methods because it converges to an approximate solution.The synthetic experiments use µ = 0.1 and compare relative error and clustering accuracy.
- Real World Data: On Hopkins155, both LADMAP variants are much faster than APG, ADM, and LADM, while accelerated LADMAP remains faster than standard LADMAP.Hopkins155 contains 156 sequences, and the comparison reports average time, iterations, and classification errors.
5 Conclusions
The paper proposes LADMAP for LRR, combining linearization, adaptive penalties, and skinny-SVD-based acceleration to reduce computational cost and improve convergence.
- Conclusions: LADMAP applies a linearized alternating direction method with adaptive penalty to the LRR problem.The method is presented as a generalization of ADM.
- Conclusions: Linearization removes the need for auxiliary variables and matrix inversions, while fewer variables and constraints accelerate convergence.The conclusion links these changes to the LADMAP formulation.
- Conclusions: Skinny-SVD representations and successive matrix-vector multiplications avoid full matrix-matrix multiplications when solving LRR.These techniques are used to accelerate partial SVD computation.
- Conclusions: The resulting LRR solver has computation complexity O(rn^2), and numerical results show faster convergence than LADM and ADM.The paper also states that LADMAP can be applied to other convex programs.
A Proof of Theorem 3
The proof shows that LADMAP accumulation points satisfy optimality conditions and that the full generated sequence converges to a KKT point of the problem.
- Proof of Theorem 3: The proof begins with a bounded sequence and selects an accumulation point (x∞, y∞, λ∞).The argument then proceeds in two steps.
- Proof of Theorem 3: The first step establishes that the selected accumulation point is a KKT point of problem (1).The proof uses feasibility and subgradient relations for the two variables.
- Proof of Theorem 3: The relation β_k(λ_{k+1} − λ_k) → 0 shows that every accumulation point of {(x_k, y_k)} is feasible.This connects the multiplier update behavior to feasibility.
- Proof of Theorem 3: Using feasibility, the proof shows that the accumulation point has objective value no larger than any feasible solution, making it optimal.The inequality concludes that (x∞, y∞) is an optimal solution to problem (1).
- Proof of Theorem 3: Because the accumulation point can be arbitrary, the whole sequence converges to a KKT point of problem (1).The proof explicitly separates convergence of the full sequence from the accumulation-point argument.