Source-linked AI summary
Learning efficient sparse and low rank models
Pablo Sprechmann, Alex M. Bronstein, Guillermo Sapiro
TL;DR
Parsimonious models are difficult to deploy when iterative optimization is too slow or hard to embed in discriminative learning. The paper replaces those solvers with learned fixed-complexity pursuit processes derived from proximal descent. These encoders approximate exact representations efficiently and support supervised extensions across image and audio applications.
Problem
Iterative parsimonious optimization has data-dependent latency and is difficult to include in discriminative learning objectives.
Method
The paper constructs learned deterministic pursuit-process encoders from proximal-descent iterations for structured sparse and robust low-rank models.
Results
The framework produces fast encoders that approximate optimization-based solutions and perform similarly to or better than iterative pursuits across multiple real applications.
Takeaways & Limitations
Parsimonious representations can serve as fast approximants, predictors, or learned modelers while supporting discriminative and alignment-related objectives.
Takeaways & Limitations
The supervised training regime is limited when testing data comes from the same class as training data, and fixed-step proximal methods can converge slowly.
Abstract
from arXiv · showhide
Parsimony, including sparsity and low rank, has been shown to successfully model data in numerous machine learning and signal processing tasks. Traditionally, such modeling approaches rely on an iterative algorithm that minimizes an objective function with parsimony-promoting terms. The inherently sequential structure and data-dependent complexity and latency of iterative optimization constitute a major limitation in many applications requiring real-time performance or involving large-scale data. Another limitation encountered by these modeling techniques is the difficulty of their inclusion in discriminative learning scenarios. In this work, we propose to move the emphasis from the model to the pursuit algorithm, and develop a process-centric view of parsimonious modeling, in which a learned deterministic fixed-complexity pursuit process is used in lieu of iterative optimization. We show a principled way to construct learnable pursuit process architectures for structured sparse and robust low rank models, derived from the iteration of proximal descent algorithms. These architectures learn to approximate the exact parsimonious representation at a fraction of the complexity of the standard optimization methods. We also show that appropriate training regimes allow to naturally extend parsimonious models to discriminative settings. State-of-the-art results are demonstrated on several challenging problems in image and audio processing with several orders of magnitude speedup compared to the exact optimization algorithms.
1 Introduction
Parsimonious models are powerful but traditionally depend on iterative optimization, which limits computational efficiency and integration with discriminative learning. The paper shifts emphasis to learned, fixed-complexity pursuit processes derived from proximal algorithms.
- Sparsity and low rank provide widely useful parsimonious representations across machine learning and signal processing.
- Iterative optimization creates sequential, data-dependent complexity and latency that can hinder real-time and large-scale applications.
- Explicit optimization solutions complicate supervised learning because higher-level objectives depend on difficult bilevel pursuit problems.
- The paper replaces iterative solvers with learned deterministic pursuit processes that approximate optimization-based representations on real data.
- Proximal-descent-derived encoder architectures cover structured sparse coding, robust PCA, and NMF.
- Online training, discriminative objectives, and transformation-aware pursuit extend the framework beyond fixed-distribution approximation.
- Experiments span image, face, audio, and speaker applications, with fast encoders performing similarly to or better than iterative processes at lower complexity.
2 Parsimonious models
The paper formulates sparse, structured-sparse, low-rank, robust PCA, and NMF models within a general optimization framework. Online variants update representations and models sequentially, while factorized formulations provide tractable alternatives for low-rank modeling.
- Parsimonious modeling optimizes a representation Z, optionally with dictionary D, using penalties that impose structure on codes and dictionaries.
- Online modeling processes sequential samples by pursuing each representation, updating the model, and optionally discounting older information with a forgetting factor.
- Sparse models: Unstructured sparse coding uses an ℓ1 regularizer and decomposes into independent column-wise pursuit problems.
- Sparse models: Structured sparsity groups coefficients so atoms are activated or deactivated according to predefined group, hierarchical, or overlapping structures.
- Low-rank models and robust PCA: Robust PCA decomposes data into low-rank, sparse-outlier, and perturbation components, using nuclear-norm regularization as a rank surrogate.
- Low-rank models and robust PCA: Factorizing the low-rank component as D0S reduces optimization variables and interprets D0 as an under-complete dictionary.
- Non-negative matrix factorization: NMF factors non-negative data into non-negative matrices, while the RNMF objective provides rank regularization and robustness to outliers but is not fully equivalent to nuclear-norm minimization.
3 Proximal methods
Proximal splitting solves nonsmooth convex problems by alternating linear-gradient and proximal transformations, with specialized operators for sparse and structured-sparse models. Fixed-step methods are simple and convergent, but their basic convergence rate is sub-linear.
- Proximal splitting: Proximal splitting decomposes the cost into a smooth convex term and a possibly nonsmooth convex term, enabling efficient optimization.The smooth term has an α-Lipschitz continuous gradient, while the proximal operator handles the nonsmooth component.
- Convergence: Fixed-step proximal algorithms have relatively slow sub-linear convergence, whereas accelerated variants can achieve linear convergence.The paper notes that accelerated methods are outside its scope.
- Sparse models: For unstructured sparsity, the proximal operator is element-wise soft thresholding, yielding the ISTA algorithm.The matrices H and W arise from the linear gradient of the data-fitting term.
- RPCA and RNMF: RNMF uses nonnegative one-sided thresholding for sparse outliers, while RPCA uses the standard thresholding operator.Both algorithms share the same fixed-step proximal-descent structure; the proximal operator distinguishes the models.
- Structured sparsity: Group sparsity uses group soft thresholding, which acts on coefficients within each group and leaves the others unchanged.For non-overlapping groups, the proximal operator is separable and can be computed independently for each group.
- Structured sparsity: Tree-structured hierarchical sparsity permits efficient proximal computation by composing level-specific operators from leaves to root.The corresponding proximal operator extends the basic algorithm to hierarchical sparse models such as HiLasso.
4 Learnable pursuit processes
The paper replaces implicit optimization-based encoders with explicitly parameterized pursuit processes derived by truncating proximal-descent iterations. Learning the process parameters can reduce approximation error at fixed complexity and incorporate data-distribution or task-specific information.
- Process-centric formulation: The process-centric framework explicitly represents both encoder and decoder, using a parametric deterministic encoder and a linear decoder.It separates selecting the pursuit-process architecture from learning its parameters.
- Process learning: Process learning selects encoder parameters by minimizing empirical risk over training examples as an approximation to expected risk.When the encoder family is sufficiently restrictive, statistical learning theory supports this substitution.
- Process learning: Training uses stochastic gradient descent with back-propagation to update differentiable encoder parameters, and SGD scales to large datasets.Each update uses a randomly selected subset of training data and a decaying step size.
- Error decomposition: The total training approximation error is decomposed into approximation, estimation, and optimization errors.The estimation error decreases with training-set size, while offline optimization error can be reduced by increasing SGD iterations.
- Process architecture: Truncated proximal-descent processes with T iterations form a feed-forward network with identical layers and parameters Θ = {W, H, t}.The untruncated family is denoted F∞, while FT contains the fixed-depth processes.
- Approximation guarantees: For convex proximal-descent objectives, the optimal unrestricted pursuit process lies in F∞, and the approximation error can be made arbitrarily small by increasing T.The convergence guarantee is worst-case and holds uniformly for every input vector.
- Complexity trade-off: At fixed computational depth, learned processes can achieve lower expected-risk approximation error by adapting to the input distribution, unlike standard iterative pursuit algorithms.The encoder complexity is proportional to T, creating a trade-off between approximation error and computation.
5 Training regimes
The paper presents unsupervised, supervised, approximation, and discriminative training regimes for process-centric parsimonious encoders. These regimes support online learning, improve modeling beyond crude RPCA/RNMF assumptions, and enable classification-oriented representations.
- Unsupervised training: Unsupervised training minimizes reconstruction loss from data alone and can combine online parameter adaptation with online dictionary updates.
- Supervised training: Supervised encoder/decoder training incorporates task-specific targets, but a fixed-decoder encoder may no longer solve the original modeling problem and creates bilevel optimization.
- Supervised training: Domain-specific supervision improves approximation of reality beyond crude RPCA/RNMF assumptions, with trained encoders outperforming unsupervised encoders and exact RPCA/RNMF algorithms.The audio example targets mixtures where music is not exactly low-rank and voice is not exactly unstructured sparse.
- Approximation: Approximation training uses supervision to reproduce optimal encoder outputs, but assumes testing data comes from the same class as training data and cannot improve the underlying model's encoder capabilities.Similar performance can nevertheless be achieved with unsupervised training.
- Discriminative training: Discriminative training extends parsimonious modeling to non-invertible representations for classification and can outperform reconstruction-trained encoder/decoder pairs on speaker identification.The loss favors low fitting error for the ground-truth speaker encoder and high fitting error for the others.
- Geometric alignment: For misaligned data, joint transformation optimization aligns inputs while retaining online trainability and avoids recomputing the entire dataset alignment as new data arrive.Without alignment, even small facial-image misalignments can degrade the low-rank representation.
6 Experimental results
Experiments evaluate fast CoD, BCoD, RPCA, and RNMF encoders across online sparse coding, structured sparse coding, geometric robust PCA, separation, and speaker identification. The encoders generally approach or improve iterative methods while using fixed or substantially lower computational complexity.
- Online sparse encoders: 30 × 10^4 patches from three Brodatz texture images evaluated unstructured CoD encoders under online learning with q = 64 atoms and T = 4 layers.Performance was measured using the Lasso objective across three consecutive patch blocks.
- Online sparse encoders: After adapting to the current data class, online CoD (Unsupervised) outperformed its offline counterpart, while CoD (Approximation) performed worst.The online encoder incurred a relatively small performance drop compared with exact Lasso while retaining tremendously lower, fixed computational complexity.
- Structured sparse encoders: Nearly a factor of two improvement resulted from using the structured BCoD architecture instead of an unstructured encoder with the same layers and dictionary.The discriminative objective further improved performance, and two-layer encoders lost only about 1% of correct classification rate.
- Robust PCA encoders with geometric optimization: RPCA encoders were trained on 600 faces and tested on 200 held-out faces plus sub-pixel translated versions to assess geometric robustness.Figure 4 compares original, shifted, and optimally realigned representations through reconstructed, low-rank, and sparse-outlier components.
- Singing voice separation: Unsupervised RNMF encoders matched exact RNMF separation performance at a fraction of its computational complexity and latency, while supervised training significantly improved separation.Audio separation quality was reported using dB SDR on the MIR-1K dataset.
- Robust speaker identification: Low rank NMF (Discriminative) encoders significantly outperformed low rank NMF (Supervised) encoders for speaker identification in mixtures contaminated by six noise categories at 0 dB SNR.The experiment used GRID speech clips from 10 distinct speakers and reported classification rates in Table 3.
7 Conclusions and future work
The framework uses learned deterministic functions to approximate optimization-based parsimonious solutions efficiently, and it can be extended beyond synthesis models to analysis cosparse models.
- The framework combines convex optimization with multi-layer neural networks to approximate parsimonious optimization solutions with substantially lower computational time.
- The proposed encoders can incorporate different objective functions at almost the same computational cost.
- The framework can naturally extend from synthesis models to analysis cosparse models, where signals are sparse in a transformed domain.
- Truncating iterative algorithms such as ADMM provides one way to define the function space used by the framework.