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

Abstract

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(r{n}^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.

Manuscript accepted by NIPS 2011

References in corpus (3)

• Multi-Task Feature Learning Via Efficient l2,1-Norm Minimization
• A Singular Value Thresholding Algorithm for Matrix Completion
• Some Software Packages for Partial SVD Computation

Cited by in corpus (99)

• Multi-View Spectral Clustering via Structured Low-Rank Matrix Factorization
• Multispectral imaging using a single bucket detector
• A Nonconvex Low-Rank Tensor Completion Model for Spatiotemporal Traffic Data Imputation
• Connections Between Nuclear Norm and Frobenius Norm Based Representations
• Multi-View Matrix Completion for Multi-Label Image Classification
• Feature Concatenation Multi-view Subspace Clustering
• Federated Tensor Factorization for Computational Phenotyping
• Iterative Views Agreement: An Iterative Low-Rank based Structured Optimization Method to Multi-View Spectral Clustering
• An Overview of Robust Subspace Recovery
• Constructing a Non-Negative Low Rank and Sparse Graph with Data-Adaptive Features
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Learning Converged Propagations with Deep Prior Ensemble for Image Enhancement
• Fixed-Rank Representation for Unsupervised Visual Learning
• Linearized Alternating Direction Method with Adaptive Penalty and Warm Starts for Fast Solving Transform Invariant Low-Rank Textures
• Constrained Bilinear Factorization Multi-view Subspace Clustering
• Subspace clustering using a symmetric low-rank representation
• Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation
• Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering
• Adaptive ADMM with Spectral Penalty Parameter Selection
• Online Structured Sparsity-based Moving Object Detection from Satellite Videos
• Adaptive Consensus ADMM for Distributed Optimization
• Efficient Background Modeling Based on Sparse Representation and Outlier Iterative Removal
• Multi-frame denoising of high speed optical coherence tomography data using inter-frame and intra-frame priors
• Symmetric low-rank representation for subspace clustering
• Robust Subspace Clustering via Tighter Rank Approximation
• Constrained Low-Rank Learning Using Least Squares-Based Regularization
• Integrative Generalized Convex Clustering Optimization and Feature Selection for Mixed Multi-View Data
• Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
• Linear Global Translation Estimation with Feature Tracks
• Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
• Fast Proximal Linearized Alternating Direction Method of Multiplier with Parallel Splitting
• RGB-T Object Tracking:Benchmark and Baseline
• Generalized Higher-Order Tensor Decomposition via Parallel ADMM
• Globally Variance-Constrained Sparse Representation and Its Application in Image Set Coding
• SLCRF: Subspace Learning with Conditional Random Field for Hyperspectral Image Classification
• Double Weighted Truncated Nuclear Norm Regularization for Low-Rank Matrix Completion
• Exclusivity Regularized Machine
• Generalized Label Enhancement with Sample Correlations
• A First-Order Algorithmic Framework for Wasserstein Distributionally Robust Logistic Regression
• Optimization Algorithm Inspired Deep Neural Network Structure Design
• On Unifying Multi-View Self-Representations for Clustering by Tensor Multi-Rank Minimization
• Hyperspectral Super-Resolution via Coupled Tensor Ring Factorization
• Masked-RPCA: Sparse and Low-rank Decomposition Under Overlaying Model and Application to Moving Object Detection
• Kernelized Low Rank Representation on Grassmann Manifolds
• Low-rank Multi-view Clustering in Third-Order Tensor Space
• Segmentation of Subspaces in Sequential Data
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation
• Efficient Constrained Tensor Factorization by Alternating Optimization with Primal-Dual Splitting
• Truncated nuclear norm regularization for low-rank tensor completion
• Accelerated Alternating Direction Method of Multipliers: an Optimal $O(1/K)$ Nonergodic Analysis
• Robust Group Subspace Recovery: A New Approach for Multi-Modality Data Fusion
• Low-Rank Hankel Tensor Completion for Traffic Speed Estimation
• Kernelized LRR on Grassmann Manifolds for Subspace Clustering
• Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization
• Block-Diagonal Sparse Representation by Learning a Linear Combination Dictionary for Recognition
• COROLA: A Sequential Solution to Moving Object Detection Using Low-rank Approximation
• Robust Tensor Recovery with Fiber Outliers for Traffic Events
• SPL-MLL: Selecting Predictable Landmarks for Multi-Label Learning
• Hierarchical Tensor Ring Completion
• Nonconvex Approach for Sparse and Low-Rank Constrained Models with Dual Momentum
• Low-Rank Matrix Completion: A Contemporary Survey
• Multiple Graph Learning for Scalable Multi-view Clustering
• Low-Rank Tensor Completion by Truncated Nuclear Norm Regularization
• SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
• Visual Tracking via Dynamic Graph Learning
• Low-Rank Representation over the Manifold of Curves
• Low Rank Representation on Riemannian Manifold of Square Root Densities
• Structured Low-Rank Matrix Factorization with Missing and Grossly Corrupted Observations
• A Group Norm Regularized Factorization Model for Subspace Segmentation
• Graph Construction with Label Information for Semi-Supervised Learning
• Fast Optimization Algorithm on Riemannian Manifolds and Its Application in Low-Rank Representation
• Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
• Differential covariance: A new method to estimate functional connectivity in fMRI
• Image Tag Completion and Refinement by Subspace Clustering and Matrix Completion
• Tensor Q-Rank: New Data Dependent Definition of Tensor Rank
• Manifold Criterion Guided Transfer Learning via Intermediate Domain Generation
• Robust Dictionary based Data Representation
• Understanding and Improving Multi-Sense Word Embeddings via Extended Robust Principal Component Analysis
• Broad Learning for Healthcare
• Coarse-to-Fine Salient Object Detection with Low-Rank Matrix Recovery
• Permutation-Invariant Subgraph Discovery
• Compressed Randomized UTV Decompositions for Low-Rank Approximations and Big Data Applications
• Fast and Robust Fixed-Rank Matrix Recovery
• Randomized Rank-Revealing UZV Decomposition for Low-Rank Approximation of Matrices
• Consistent and Complementary Graph Regularized Multi-view Subspace Clustering
• Automated quantitative analysis of first-pass myocardial perfusion magnetic resonance imaging data
• Tensor Full Feature Measure and Its Nonconvex Relaxation Applications to Tensor Recovery
• A Robust Compressive Quantum State Tomography Algorithm Using ADMM
• Superpixel-guided Discriminative Low-rank Representation of Hyperspectral Images for Classification
• RGB-T Image Saliency Detection via Collaborative Graph Learning
• Estimation of Graphical Models through Structured Norm Minimization
• Tractable Clustering of Data on the Curve Manifold
• Leveraging Union of Subspace Structure to Improve Constrained Clustering
• Study of Compressed Randomized UTV Decompositions for Low-Rank Matrix Approximations in Data Science
• A Nonconvex Proximal Splitting Algorithm under Moreau-Yosida Regularization
• Image Denoising by Gaussian Patch Mixture Model and Low Rank Patches
• Partial Sum Minimization of Singular Values Representation on Grassmann Manifolds
• Optimal Graph Laplacian
• Subspace Clustering Based Tag Sharing for Inductive Tag Matrix Refinement with Complex Errors