# Dictionary-based Low-Rank Approximations and the Mixed Sparse Coding problem

arXiv: https://arxiv.org/abs/2111.12399 · HTML: https://mlsanity.com/paper/2111.12399/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 81 references that are in the map.
- First posted on arXiv 24 Nov 2021.

## Builds on (most cited first, 20 of 20)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Tensor Regression Networks](https://mlsanity.com/paper/1707.08308/) (2017)
- [Fast Hyperspectral Image Denoising and Inpainting Based on Low-Rank and Sparse Representations](https://mlsanity.com/paper/2103.06842/) (2021)
- [On Identifiability of Nonnegative Matrix Factorization](https://mlsanity.com/paper/1709.00614/) (2017)
- [SLOPE - Adaptive variable selection via convex optimization](https://mlsanity.com/paper/1407.3824/) (2014)
- [Hyperspectral Unmixing: Ground Truth Labeling, Datasets, Benchmark Performances and Survey](https://mlsanity.com/paper/1708.05125/) (2017)
- [A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization](https://mlsanity.com/paper/1506.04209/) (2015)
- [Covariance Estimation in High Dimensions via Kronecker Product Expansions](https://mlsanity.com/paper/1302.2686/) (2013)
- [Stochastic Gradients for Large-Scale Tensor Decomposition](https://mlsanity.com/paper/1906.01687/) (2019)
- [Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective](https://mlsanity.com/paper/2006.08183/) (2020)
- [Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization](https://mlsanity.com/paper/1302.4385/) (2013)
- [Alternating proximal gradient method for sparse nonnegative Tucker decomposition](https://mlsanity.com/paper/1302.2559/) (2013)
- [A Flexible Optimization Framework for Regularized Matrix-Tensor Factorizations with Linear Couplings](https://mlsanity.com/paper/2007.09605/) (2020)
- [Uncovering audio patterns in music with Nonnegative Tucker Decomposition for structural segmentation](https://mlsanity.com/paper/2104.08580/) (2021)
- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Identifiability of Complete Dictionary Learning](https://mlsanity.com/paper/1808.08765/) (2018)
- [Dictionary-based Tensor Canonical Polyadic Decomposition](https://mlsanity.com/paper/1704.00541/) (2017)
- [PARAFAC2 AO-ADMM: Constraints in all modes](https://mlsanity.com/paper/2102.02087/) (2021)
- [The fastest ℓ1,∞ prox in the west](https://mlsanity.com/paper/1910.03749/) (2019)
- [Computing the proximal operator of the ℓ1 induced matrix norm](https://mlsanity.com/paper/2005.06804/) (2020)

## Abstract (arXiv)

Constrained tensor and matrix factorization models allow to extract interpretable patterns from multiway data. Therefore identifiability properties and efficient algorithms for constrained low-rank approximations are nowadays important research topics. This work deals with columns of factor matrices of a low-rank approximation being sparse in a known and possibly overcomplete basis, a model coined as Dictionary-based Low-Rank Approximation (DLRA). While earlier contributions focused on finding factor columns inside a dictionary of candidate columns, i.e. one-sparse approximations, this work is the first to tackle DLRA with sparsity larger than one. I propose to focus on the sparse-coding subproblem coined Mixed Sparse-Coding (MSC) that emerges when solving DLRA with an alternating optimization strategy. Several algorithms based on sparse-coding heuristics (greedy methods, convex relaxations) are provided to solve MSC. The performance of these heuristics is evaluated on simulated data. Then, I show how to adapt an efficient MSC solver based on the LASSO to compute Dictionary-based Matrix Factorization and Canonical Polyadic Decomposition in the context of hyperspectral image processing and chemometrics. These experiments suggest that DLRA extends the modeling capabilities of low-rank approximations, helps reducing estimation variance and enhances the identifiability and interpretability of estimated factors.