Low rank representation.pdf

Low Rank Representation – Theories and Applications 林宙辰 北京大学 April 13, 2012 TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAAAAAAAAA ? Outline ? Low Rank Representation ? Some Theoretical Analysis ? Applications ? Generalizations ? m in r a n k (A ) ; s : t : D = ?- (A ) : Sparse Subspace Clustering ? Sparse Representation ? Sparse Subspace Clustering min jjx jj0 ; s:t: y = Ax: (1) min jjzi jj0 ; s:t: x i = X i?zi ; 8i: (2) where X i? = [x1 ;￠￠￠; x i? 1 ; xi+1 ; ￠￠￠; xn ]. min jjZ jj0 ; s:t: X = X Z; diag (Z ) = 0: (3) min jjZ jj1 ; s:t: X = X Z; diag (Z ) = 0: (4) Elhamifar and Vidal. Sparse Subspace Clustering. CVPR2009. Sparse Subspace Clustering ? Construct a graph ? Normalized cut on the graph W = (jZ ¤j + j(Z ¤)T j)=2 Elhamifar and Vidal. Sparse Subspace Clustering. CVPR2009. Sparse Subspace Clustering Theorem. Assume the data is clean and is drawn from independent subspaces, then Z ¤ is block diagonal. dim ( P i S i) = P i dim (S i): Elhamifar and Vidal. Sparse Subspace Clustering. CVPR2009. Drawback of SSC ? Sensitive to noise: no cross validation among coefficients Elhamifar and Vidal. Sparse Subspace Clustering. CVPR2009. min jjzi jj1 ; s:t: x i = X zi ; (zi)i = 0: (5) min jjZ jj1 ; s:t: X = X Z; diag (Z ) = 0: (4) Hints from 2D Sparsity ? Rank is a good measure of 2D sparsity – Real data usually lie on low-dim manifolds – Low rank ? high correlation among rows/columns low-dim subspaces → low rank data matrices 1B dim Low Rank Representation min jjZ jj1 ; s:t: X = X Z; diag (Z ) = 0: (4) min jjZ jj¤; s:t: X = X Z: (6) jjZ jj¤ = P j ?j (Z ), nuclear norm, a convex surrogate of rank. no additional constraint! Liu, Lin, and Yu. Robust Subspace Segmentation by Low-Rank Representation, ICML 2010. Low Rank Representation Theorem . Assume the data is clean and is drawn from independent subspaces, then there exists Z ¤ which is blo ck diagonal, and the r