Sparse manifold transform linearizes non-linear signal transformations.
problem Non-linear signal transformations in sensory data.
method Combines sparse coding, manifold learning, and slow feature analysis.
result Models sparse discreteness and low-dimensional manifold structure in natural scenes.
Sparse Transformers can approximate dense Transformers with only O(n) connections.
problem Can sparse Transformers approximate arbitrary sequence-to-sequence functions?
method Proposed sufficient conditions for universal approximation and proved that sparse Transformers with O(n) connections can approximate dense models.
result Sparse Transformers with O(n) connections can approximate the same function class as dense models with n^2 connections.
A method for learning sparse transformations through backpropagation.
problem Sparse transformations in deep learning architectures are hard to design and often represented densely during learning.
method Adaptive, sparse hyperlayer with randomly sampled connections to overcome gradient issues.
result Trained models achieve competitive performance on real data.
Transformers excel at sparse token selection, surpassing FCNs in both worst and average cases.
problem Sparse token selection task
method One-layer transformer trained with gradient descent
result Transformers learn sparse token selection and exhibit strong out-of-distribution length generalization
Sparse transformer architecture improves accuracy and speed in generative modeling and inverse problems.
problem Improving accuracy and speed in generative modeling and inverse problems.
method Proposes a sparse transformer architecture using regularized Wasserstein proximal operator with L1 prior. result Sparse transformer achieves higher accuracy and faster convergence than classical methods.
Predictive Sparse Manifold Transform learns dynamic video sequences.
problem Learning and predicting natural dynamics in video sequences.
method Two-layer framework: sparse coding and manifold learning.
result PSMT with dynamic embedding space outperforms static baselines in future frame prediction.
Wavelet-based method for sparse data on manifolds.
problem Sparse representation of manifold-valued data.
method Interpolatory wavelet/multiscale transform for sparse regularization.
result Well-posedness of variational models and successful numerical algorithms.
SGPA calibrates transformer uncertainty for safety-critical tasks.
problem Uncertainty estimation in transformer models for safety-critical domains.
method Bayesian inference in transformer's output space using sparse Gaussian processes.
result SGPA-based Transformers improve in-distribution calibration and out-of-distribution robustness.
Sparse Transformers degrade semantic information first, with early layers encoding more.
problem Understanding how sparse Transformers affect learned representations and semantic information.
method Probed Transformers with progressively pruned weights to observe changes in semantic information and model behavior.
result Complex semantic information is first to degrade in sparse Transformers, with early layers encoding more.
Transformers learn sparse Boolean functions through RL and SFT, revealing distinct learning behaviors.
problem Learning sparse Boolean functions with Transformers.
method Reinforcement Learning (RL) with process rewards and Supervised Fine-Tuning (SFT).
result RL learns the whole CoT chain simultaneously, while SFT learns step by step.
Sparse Transformers reduce memory and time requirements for long sequence modeling.
problem Quadratic growth in memory and time with transformer sequence length.
method Sparse factorizations of attention matrix, deeper network training, attention matrix recomputation, fast attention kernels.
result Sparse Transformers can model sequences up to tens of thousands of timesteps with hundreds of layers.
Adaptively sparse Transformers improve interpretability and diversity in NLP.
problem Standard Transformers use dense attention, limiting interpretability and diversity.
method Introduces adaptively sparse Transformers using α-entmax for context-dependent sparsity. result Improves interpretability and diversity in NLP tasks without sacrificing accuracy.
Minimalistic unsupervised learning with sparse manifold transform achieves SOTA performance.
problem Achieving state-of-the-art unsupervised learning performance without complex engineering.
method Sparse manifold transform, leveraging sparse coding, manifold learning, and slow feature analysis.
result 99.3% KNN top-1 accuracy on MNIST, 81.1% on CIFAR-10, and 53.2% on CIFAR-100.
Self-attention prefers sparse functions of input sequences, reducing sample complexity.
problem Understanding the inductive biases of self-attention in modeling long-range dependencies.
method Theoretical analysis and synthetic experiments to probe sample complexity of learning sparse functions with Transformers.
result Bounded-norm Transformer networks can represent sparse functions of the input sequence with logarithmic sample complexity.
Transform learning improves MRI image reconstruction from sparse data.
problem Efficiently reconstruct MRI images from limited data.
method TL-based methods using learned models and transform domains.
result TL-based methods outperform classical CS methods in MRI reconstruction.
A new model improves CT image quality from low-dose scans.
problem Improving CT image quality from low-dose scans.
method Multi-layer Residual Sparsifying Transform (MRST) learning model for low-dose CT reconstruction.
result The MRST model outperforms conventional methods in maintaining subtle details.
The paper proposes efficient dictionary learning algorithms that avoid multiplications for sparse representations.
problem Sparse representation with reduced computational complexity.
method Factorizations of the dictionary into binary orthonormal, scaling, and shear transformations with closed-form solutions.
result The proposed methods are effective and can be compared to well-known transforms like FFT and DCT.
A new method for estimating sparse inverse covariance matrices.
problem Recovering the connectivity and non-connectivity graph of covariates.
method Adaptive thresholding in a transformed domain of the inverse covariance matrix.
result The proposed method outperforms state-of-the-art methods in accuracy.
Global Memory Augmentation (GMAT) improves Transformer performance on long documents.
problem Large memory requirements of Transformer pairwise dot-product attention for long sequences.
method Integrates a dense global memory of length M into sparse Transformer blocks.
result Significant improvement on various tasks, including synthetic tasks, masked language modeling, and reading comprehension.
A new iterative low complexity algorithm has been presented for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT, where N is a power of two and K=O(Nα), scales sub-linearly in N for some 0<α<1. Assuming a random support model for the non-zero transform domain…
SPARTAN learns sparse interaction graphs between objects in scenes.
problem Capturing structured interactions between entities in complex settings remains challenging.
method SPARTAN is a Transformer-based world model that learns sparse, context-dependent interaction graphs through sparsity regularization on attention patterns.
result SPARTAN achieves significantly improved few-shot adaptation to dynamics changes and robustness against distractors.
Efficiently computes sparse signature coefficients using kernels.
problem Lack of efficient methods for sparse signature coefficients.
method Signature kernels and PDE-based methods.
result Sparse groups of signature coefficients can be isolated effectively.
Transformers learn to integrate information from past positions incrementally, specializing heads in distinct patterns.
problem How transformers learn to integrate information from multiple past positions with varying statistical significance.
method High-order Markov chain task, incremental learning, sparse attention patterns, simplified differential equations, stage-wise convergence, early stopping as regularizer.
result Transformers learn to specialize heads in distinct patterns, shifting from competitive to cooperative learning dynamics.
New algorithms learn sparse set functions in non-orthogonal Fourier bases.
problem Learning sparse set functions in non-orthogonal Fourier bases.
method Novel algorithms using non-orthogonal Fourier transforms.
result At most nk−klog2k+k queries for k non-zero Fourier coefficients. CoT improves transformer sample efficiency by reducing input token dependencies and attention sparsity.
problem Transformer sample inefficiency in simple tasks.
method Demonstrated through parity-learning setup, showing CoT reduces required samples from exponential to polynomial.
result Transformer learns function within polynomial samples with CoT, requiring exponential samples without CoT.
Transformers can learn optimal variable selection in group-sparse classification.
problem Understanding how transformers leverage attention to select relevant variables in group-sparse classification.
method Training a one-layer transformer using gradient descent to select variables from one group of input variables.
result A one-layer transformer can correctly leverage the attention mechanism to select variables, disregarding irrelevant ones.
New GPU kernels boost deep learning speed and memory efficiency.
problem Sparse deep learning matrices are not well-suited for existing sparse kernels.
method Identified favorable properties of sparse matrices from deep learning, developed high-performance GPU kernels for sparse matrix operations.
result 27% of single-precision peak performance on Nvidia V100 GPUs achieved with new kernels.
Data is said to follow the transform (or analysis) sparsity model if it becomes sparse when acted on by a linear operator called a sparsifying transform. Several algorithms have been designed to learn such a transform directly from data, and data-adaptive sparsifying transforms have demonstrated excellent performance i…
3BASiL-TM decomposes LLMs into sparse and low-rank matrices for efficient compression.
problem Efficiently compressing large language models without significant performance loss.
method 3-Block ADMM method and transformer-matching refinement step for sparse plus low-rank decomposition.
result 3BASiL-TM reduces perplexity gap by over 30% and speeds up compression by 2.5x.
We find a closed-form determinant for a specific sparse covariance matrix model.
problem Finding the determinant of a specific class of sparse positive definite matrices.
method Using Fourier transform of local factors, Normal Factor Graph Duality Theorem, and Matrix Determinant Lemma.
result We derive a closed-form expression for the determinant.
Transformers exhibit sparse activation maps, reducing computational load and improving robustness.
problem Sparse activation in Transformer models.
method Extensive experiments on various Transformer architectures and tasks.
result Sparsity in Transformers is a prevalent phenomenon, reducing FLOP count and improving model robustness.
BigBird improves transformer performance on NLP tasks with longer sequences.
problem Quadratic dependency on sequence length in transformer models.
method Sparse attention mechanism reducing quadratic dependency to linear.
result Significant improvement in performance on NLP tasks like QA and summarization.
Proposes a sparse linear classifier for classification with pairwise dependencies.
problem Classification accuracy is limited by tree-structured graphical models.
method Semi-parametric approach using sparse linear combination of univariate and bivariate log-transformed densities.
result SLB classifier is competitive with popular methods.
Transformers show strengths and weaknesses in complexity analysis.
problem Understanding the strengths and limitations of attention layers in transformers.
method Analysis of representation power through complexity parameters and task-specific constructions.
result Transformers can solve sparse averaging tasks with logarithmic complexity, but triple detection tasks require linear complexity.
Quantum Ridgelet Transform speeds up neural network learning.
problem Efficiently finding sparse trainable subnetworks in neural networks.
method Developed a quantum ridgelet transform (QRT) for linear runtime.
result Quantum Ridgelet Transform efficiently finds sparse trainable subnetworks.
A new hashing method improves accuracy by learning an orthogonal transform.
problem Improving hashing accuracy for similarity search.
method Procrustean Orthogonal Sparse Hashing (POSH) method.
result POSH outperforms state-of-the-art hashing methods.
New algorithm improves sparse-view tomography without needing ground-truth data.
problem Poor image reconstructions with sparse projections and non-uniform sensors.
method Unsupervised deep learning with CNN and STN modules.
result Significantly outperforms filtered backprojection in sparse-view scenarios.
This work solves TRPCA under linear transforms, recovering low-rank and sparse components.
problem Exact recovery of tensor low-rank and sparse components from their sum.
method Convex optimization with weighted tensor nuclear norm and ℓ1-norm.
result The convex program exactly recovers the components under certain incoherence conditions.
Mobile V-MoEs scale down ViTs for resource-constrained vision tasks.
problem Scaling down Vision Transformers for resource-constrained applications.
method Sparse Mixture-of-Experts (MoEs) applied to entire images, with a stable training procedure.
result Mobile V-MoEs achieve better performance-efficiency trade-offs than dense ViTs.
Generates high-quality images using sparse DCT representations.
problem Challenges in generating images due to high dimensionality.
method Transformers trained on sparse DCT block sequences.
result Competitive image generation quality with state-of-the-art methods.
Canonical correlation analysis (CCA) is a multivariate statistical technique for finding the linear relationship between two sets of variables. The kernel generalization of CCA named kernel CCA has been proposed to find nonlinear relations between datasets. Despite their wide usage, they have one common limitation that…
New algorithm defends against adversarial examples in image classification.
problem Defending against adversarial examples in image classification.
method Approximates Discrete Fourier transform of sparse signals corrupted by L0 noise. result Successfully defends against L0 adversaries in image classification. ANT learns sparse embeddings for large vocabularies efficiently.
problem Lack of scalable methods for embedding large vocabularies in neural networks.
method Anchor & Transform (ANT) algorithm that learns a small set of anchor embeddings and a sparse transformation matrix.
result ANT achieves stronger performance with fewer parameters (up to 40x compression) compared to existing methods.
Efficient sparse attention reduces self-attention complexity and improves model performance.
problem Quadratic compute and memory requirements of self-attention for long sequences.
method Content-based sparse attention with dynamic routing module.
result Routing Transformer achieves state-of-the-art performance on various benchmarks.
This paper investigates efficient Transformers and finds they scale with problem size.
problem Finding suitable replacements for standard Transformers in large-scale tasks.
method Modeling efficient Transformers (Sparse and Linear) as Dynamic Programming problems and analyzing their reasoning capabilities.
result Efficient Transformers scale with problem size, but can be more efficient for certain DP problems.
Sparse JL with higher sparsity improves feature hashing accuracy.
problem Efficiently reducing high-dimensional feature vectors to lower dimensions.
method Sparse Johnson-Lindenstrauss transform with varying sparsity levels.
result Sparse JL with sparsity greater than 1 provides better norm preservation.
In this paper, we study a fast approximation method for {\it large-scale high-dimensional} sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional vectors into a low-dimensional space. In particular, we propose to apply the JL transforms to …
A new quasi-Newton method tackles NMF with transform learning on orthogonal manifolds.
problem Efficiently learning transforms for NMF in non-convex optimization on orthogonal manifolds.
method Derives a quasi-Newton method on the orthogonal matrix manifold using sparse approximations of the Hessian.
result Outperforms state-of-the-art methods by orders of magnitude in experiments on synthetic and real audio data.