Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps
From MaRDI portal
Publication:5088658
DOI10.1137/21M1438992zbMath1492.65125arXiv2105.05879OpenAlexW3163010921MaRDI QIDQ5088658
David J. Gross, Tim Fuchs, Richard Kueng, Dustin G. Mixon, Felix Krahmer
Publication date: 13 July 2022
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.05879
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Linear transformations, semilinear transformations (15A04) Randomized algorithms (68W20) Numerical linear algebra (65F99)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A multiscale sub-linear time Fourier algorithm for noisy data
- Matrix multiplication via arithmetic progressions
- Combinatorial sublinear-time Fourier algorithms
- The Mailman algorithm: a note on matrix-vector multiplication
- A note on compressed sensing and the complexity of matrix multiplication
- On tight t-designs in compact symmetric spaces of rank one
- An introduction to finite tight frames
- The cosparse analysis model and algorithms
- Improved approximation guarantees for sublinear-time Fourier algorithms
- High-dimensional sparse Fourier algorithms
- Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
- Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
- A sample efficient sparse FFT for arbitrary frequency candidate sets in high dimensions
- Explicit universal sampling sets in finite vector spaces
- Gaussian elimination is not optimal
- High-dimensional sparse FFT based on sampling along multiple rank-1 lattices
- How to Integrate a Polynomial over a Sphere
- Improved bound for complexity of matrix multiplication
- Spreads, Translation Planes and Kerdock Sets. II
- Powers of tensors and fast matrix multiplication
- Near-optimal sparse fourier representations via sampling
- Combinatorial Algorithms for Compressed Sensing
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Spreads, Translation Planes and Kerdock Sets. I
- Z4 -Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets
- Learning Sparsifying Transforms
- $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
- Fast Orthonormal Sparsifying Transforms Based on Householder Reflectors
- Learning Fast Sparsifying Transforms
- Analysis of quickselect : an algorithm for order statistics
- Dictionary Learning for Stereo Image Representation
- Nearly optimal sparse fourier transform
- Multiplying matrices faster than coppersmith-winograd
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
This page was built for publication: Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps
