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

By Zhouchen Lin, Risheng Liu, Zhixun Su. 2011

1,297 citations recorded by the source corpus.

Many machine learning and signal processing problems can be formulated as linearly constrained convex programs, which could be efficiently solved by the alternating direction method (ADM). However, usually the subproblems in ADM are easily solvable only when the linear mappings in the constraints are identities. To address this issue, we propose a linearized ADM (LADM) method by linearizing the quadratic penalty term and adding a proximal term when solving the sub-problems. For fast convergence, we also allow the penalty to change adaptively according a novel update rule. We prove the global convergence of LADM with adaptive penalty (LADMAP). As an example, we apply LADMAP to solve low-rank representation (LRR), which is an important subspace clustering technique yet suffers from high computation cost. By combining LADMAP with a skinny SVD representation technique, we are able to reduce the complexity O(n3) of the original ADM based method to O(rn2), where r and n are the rank and size of the representation matrix, respectively, hence making LRR possible for large scale applications. Numerical experiments verify that for LRR our LADMAP based methods are much faster than state-of-the-art algorithms.

Subfields: Aerospace Engineering, Computational Mechanics, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

1. Thierry Bouwmans
2. Lei Zhang
3. Dacheng Tao
4. Haibin Ling
5. Wangmeng Zuo
6. Xiangchu Feng
7. Deyu Meng
8. Qi Xie

In Computational Mechanics

1. Lei Zhang
2. Wangmeng Zuo
3. Xuelong Li
4. Xiangchu Feng
5. Thierry Bouwmans
6. Deyu Meng
7. Dacheng Tao
8. Zhouchen Lin

In Signal Processing

1. Thierry Bouwmans
2. Dacheng Tao
3. Lei Zhang
4. Dong Xu
5. Xiangchu Feng
6. Xuelong Li
7. Haibin Ling
8. Deyu Meng

Citations in the corpus

• Federated Tensor Factorization for Computational Phenotyping (2017, background): “Augmented Lagrangian function L for the new optimization problem (5) is k and Y ( n ) are the Lagrangian multipliers. penalty terms that are multiplied by parameter ω and µ help L to improve the convergence property (i.e., method of multiplier ) [23] during federated optimization in Section 4.3.”
• Weighted Nuclear Norm Minimization with Application to Image Denoising (2014, methodology): “Low rank matrix approximation methods can be generally categorized into two categories: the low rank matrix factorization (LRMF) methods [25, 2, 16, 13] and the nuclear norm minimization (NNM) methods [14, 4, 27, 3, 20, 19, 21, 11].”
• A BaSiC tool for background and shading correction of optical microscopy images (2017, methodology): “Details of all WSIs and the corresponding corrections are included in Supplementary Figs 5–8.”
• Salient Object Detection via Structured Matrix Decomposition (2017, methodology): “ADM-SMD Input: Feature matrix F , parameters a ; b , index tree T ¼ f G ij g and tree node weight v ij (default as 1).”
• Cognitive Internet of Things: A New Paradigm Beyond Connection (2014, methodology): “Readers can tailor the theoretical results in [36]–[39] and references therein to their specific CIoT applications of interest.”
• RGB-T Object Tracking: Benchmark and Baseline (2018, methodology): “It is worth noting that we jointly solve modality weights, sparse representations, and the graph (including graph structure, edge weights and node weights) in a single optimization framework by designing an efficient ADMM (Alternation Direction Method of Multipliers) algorithm [16].”
• DP-ADMM: ADMM-Based Distributed Learning With Differential Privacy (2018, methodology): “Linearized ADMM [24], [25] replaces the quadratic function in the augmented Lagrangian function with a linearized approximation and thus provides a better way to solve subproblems without closedform solutions.”
• Kronecker-Basis-Representation Based Tensor Sparsity and Its Applications to Tensor Recovery (2018, methodology): “Various ameliorations have been further proposed for this task [28], [38].”
• Essential Tensor Learning for Multi-View Spectral Clustering (2018, methodology): “In [31], the convergence of ADMM with two blocks of variables has already been proved.”
• A survey of machine learning for big data processing (2016, methodology): “The problem formulated in (3) shows the fundamental task of the research on matrix recovery for high-dimensional data processing, which can be efficiently solved by some existing algorithms including augmented Lagrange multipliers (ALM) algorithm and accelerated proximal gradient (APG) algorithm [90”
• Anomaly Detection in Hyperspectral Images Based on Low-Rank and Sparse Representation (2016, methodology): “Thus, a newly developed method called the linearized alternating direction method with adaptive penalty (LADMAP) [30] is adopted to solve (6).”
• Latent Multi-view Subspace Clustering (2017, methodology): “The Augmented Lagrange Multiplier (ALM) with Alternating Direction Minimizing (ADM) strategy [17] is an efficient and effective solver for our problems.”
• LIME: Low-Light Image Enhancement via Illumination Map Estimation (2017, methodology): “The proposed Algorithm 1 follows the framework of Augmented Lagrangian Multiplier with Alternating Direction Minimizing (ALM-ADM), the theoretical guarantee of which has been well established for twoblock convex cases [26], [27].”
• On Unifying Multi-view Self-Representations for Clustering by Tensor Multi-rank Minimization (2016, methodology): “(23) where the matrixYv and the tensor W represent two Lagrange multipliers, μ and ρ are actually the penalty parameters, which are adjusted by using adaptive updating strategy as suggest ed in [26].”
• Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization (2013, methodology): “also show that ADMM with an adaptive penalty parameter could speed up the convergence of ADMM [39].”
• Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “The iteration complexity was analyzed for Multi-Block ADMM [225].”
• Rubik: Knowledge Guided Tensor Factorization and Completion for Health Data Analytics (2015, background): “{ η, µ } are penalty parameters, which can be adjusted efficiently according to [21].”
• Traditional and recent approaches in background modeling for foreground detection: An overview (2014, methodology): “[108] adapted the RPCA-PCP with Linearized Alternating Direction Method with Adaptive Penalty [166].”
• Multiview Spectral Clustering via Structured Low-Rank Matrix Factorization (2017, methodology): “7 Update E i : Update µ according to [ Lin et al. , 2011 ] 16 whether converged Remove the i th view from the view set as Following [Wang et al. , 2016a], µ is tuned using the adaptive updating strategy [Lin et al. , 2011] to yield a faster convergence.”