Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation

Details Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation

2011-09-02

arxiv.org/abs/1109.0367v1

Mathematics

Optimization and Control

Manuscript accepted by NIPS 2011

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-687440