  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.
