Sparse Coding Representation of 2-way Data

Boya Ma, Abram Magner, Maxwell McNeil, Petko Bogdanov · 2025

Read Sparse Coding Representation of 2-way Data by Boya Ma, Abram Magner, Maxwell McNeil, Petko Bogdanov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10033.txt.

Introduction

Boya Ma and 3 co-authors tackle learning several dictionaries at once for sparse coding in a 2025 signal processing paper. Sparse coding writes a signal as a blend of a few atoms drawn from dictionaries, and pairing a time dictionary with a space dictionary suits data that varies in both. Fixed dictionaries from classical transforms are cheap but blunt, while learned ones fit better at the price of a hard joint learning problem across every atom pairing.

Their low-rank coding model for two dictionaries restores order, and they bound how many samples learning needs before the dictionaries generalise to fresh data. An alternating convex method called AODL swaps between polishing the codes and polishing the dictionaries. Demonstrations check that the recovered representations stay faithful on realistic material.

Catalog record

CREATORBoya Ma, Abram Magner, Maxwell McNeil, Petko Bogdanov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-10033

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sparse Coding Representation of 2-way Data Boya Ma, Abram Magner, Maxwell McNeil, Petko Bogdanov Abstract Sparse dictionary coding represents signals as linear combinations of a few dictionary atoms. It has been applied to images, time series, graph signals and multi-way spatio-temporal data by jointly employing temporal and spatial dictionaries. Data-agnostic analytical dictionaries, such as the discrete Fourier transform, wavelets and graph Fourier, have seen wide adoption due to efficient implementations and good practical performance. On the other hand, dictionaries learned from data offer sparser and more accurate solutions but require learning of both the dictionaries and the coding coefficients. This becomes especially challenging for multi-dictionary scenarios since encoding coefficients correspond to all atom combinations from the dictionaries. To address this challenge, we propose a low-rank coding model for 2-dictionary scenarios and study its data complexity. Namely, we establish a bound on the number of samples needed to learn dictionaries that generalize to unseen samples from the same distribution. We propose a convex relaxation solution, called AODL , whose exact solution we show also solves the original problem. We then solve this relaxation via alternating optimization between the sparse coding matrices and the learned dictionaries, which we prove to be convergent. We demonstrate its quality for data reconstruction and missing value imputation in both synthetic and real-world datasets. For a fixed reconstruction quality, AODL learns up to 90 % 90\% sparser solutions compared to non-low-rank and analytical (fixed) dictionary baselines. In addition, the learned dictionaries reveal interpretable insights into patterns present within the samples used for training. 1 Introduction Sparse dictionary-based coding has been employed for signal and image processing 10.1609/aaai.v26i1.8297 ; adler2015sparse , machine learning multilabel2021aaai ; evtimova2021sparse ; sulam2020adversarial , compressed sensing ji2008bayesian and data analytics TGSD ; MDTD ; shuman2013emerging ; Sandryhaila2014 . In the sparse-coding framework, observed data is represented as a linear combination of vectors called dictionary atoms. Dictionaries can be either derived analytically or learned from data. Commonly adopted analytical dictionaries include the discrete Fourier transform (DFT), wavelets, and the Ramanujan periodic basis tennetiTSP2015 . While they provide structured priors such as signal smoothness over a graph structure via the GFT dong2019learning or periodicity via the Ramanujan dictionary tennetiTSP2015 , they may fall short in enabling sparse and accurate representations for data with patterns that do not align well with the predefined atoms. An alternative approach is to learn the dictionaries directly from data which has been shown to enable higher compression rates and better representation quality rubinstein2010dictionaries . The input in the dictionary learning problem is a set of (training) signals, and the goal is to learn both a dictionary and corresponding encoding coefficients for the input aharon2006k ; hawe2013separable ; shahriari2021new ; pati1993orthogonal . While many existing techniques focus on 1D (vector) input signals, multi-mode samples require learning dictionaries for each mode. For example, spatiotemporal signals could be sparsely coded by employing jointly a spatial dictionary with atoms corresponding to spatial localities and temporal dictionary with atoms corresponding to trends in time TGSD . Multi-dictionary sparse coding with fixed (analytical) dictionaries was demonstrated beneficial for a range of downstream tasks like compression, missing value imputation, and community detection TGSD ; ur2023time ; MDTD . Learning dictionaries from data in the multi-way setting requires i) learning multiple dictionaries and ii) estimating coding coefficients which correspond to combinations of atoms. An early two-way (2D) dictionary learning method SeDiL hawe2013separable promotes full rank dictionaries and atom coherence within a geometric conjugate gradient optimizer for the dictionary learning step. Follow-up works zhang2017analytic ; zhang2016improved improve on the original method by adopting 2D-OMP fang20122d and FISTA beck2009fast for the sparse coding step. The latest methods in this category MOD and CMOD shahriari2021new employ gradient projection for dictionary learning. A common limitation of all existing methods is that they do not impose any structure (beyond the usual sparsity) on the encoding matrices. In the 2D case the number of coefficients grows quadratically with the sizes (number of atoms) of the left and right dictionaries. This rate of growth of the coding matrices makes the iterative learning of dictionaries and encoding challenging. (a) Data model employed by AODL . (b) Low v.s. unrestricted rank. Figure 1: 1(a) AODL model: \mathcal{X} is a set of data sample matrices, L and R are shared dictionaries and Y,W are sets of “slim” sample-specific coding matrices. 1(b) Comparison of low-rank (LYWR) and unrestricted rank (LZR) coding representations for Road traffic data. Both representations are estimated using an ADMM sparse solver with analytical (GFT and Ramanujan) dictionaries for a single data matrix X . To address the above challenge we propose the 2D dictionary learning problem with low-rank coding matrices. The data model is schematically depicted in Fig. 1(a) where the input signals X correspond to different snapshots of user-transportation preference matrices from some organization. We model the inputs as a product of shared left (user) L and right (transportation type) R dictionaries and a set of low-rank encoding matrices represented as the product YW . The inner dimension (columns of Y and rows of W ) determines the rank of the encoding matrix. Beyond limiting the number of coefficients generating the data, this representation allows us to capture patterns of shared behavior in the learned dictionary atoms, e.g, persistent groups of users who prefer specific types of transportation for the data example from Fig. 1(a) . In addition, the low-rank coding model enables more succinct representations of spatio-temporal data as demonstrated in Fig. 1(b) which compares the error and model sizes of the low rank model (LYWR) and an unconstrained rank model (LZR) with fixed dictionaries (only sparse coding). We bound the data complexity of our low-rank dictionary learning problem and propose an alternating minimization solution AODL which outperforms baselines in terms of data reconstruction quality and missing value imputation on multiple datasets. Our contributions in this work are as follows: \bullet Novelty: To the best of our knowledge, we are the first to pose the problem of multi-dictionary learning for low-rank sparse coding. \bullet Theoretical analysis: We derive a data-distribution-independent sample complexity bound for 2D dictionary learning and show empirical support for this bound. We prove that the general sparsity constrained problem can be solved as an L_{1} regularization objective for which we propose an efficient and provably convergent optimization procedure AODL . \bullet Accuracy: Our proposed method AODL consistently produces encodings with lower representation error compared to the closest baselines for a fixed number of coding coefficients (model size). It also imputes missing values more accurately than alternative techniques. \bullet Compactness: To achieve the same level of reconstruction quality, our approach saves up to 90\% of the coefficients compared to the closest baselines in large real-world datasets. 2 Related Work Sparse coding is widely employed in signal processing zhang2015survey ; rubinstein2010dictionaries ; GIST , image analysis elad2006image and computer vision wright2008robust . Existing methods can be grouped into three main categories: convex optimization solutions, non-convex techniques, and greedy algorithms marques2018review . Relaxation techniques impose sparsity on the coding coefficients via L1 regularizers TGSD ; MDTD , while greedy algorithms select one atom at a time wang2012generalized ; de2017sparsity ; lee2016sparse . Most existing methods focus on 1D signals while we focus on

Read the complete text