Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps
Authors:
- Tim FuchsTFTim Fuchs
- David GrossDGDavid Gross
- Felix KrahmerFKFelix Krahmer
- Richard KuengRKRichard Kueng
- Dustin MixonDMDustin Mixon
- 21 June 2022
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 43 (2) , 939-952
Abstract
Given an arbitrary matrix $A\in\mathbb{R}^{m\times n}$, we consider the fundamental problem of computing $Ax$ for any $x\in\mathbb{R}^n$ such that $Ax$ is $s$-sparse. While fast algorithms exist fo...
Keywords
All Related Versions
Funding Information
- Air Force Office of Scientific Research (FA9550-18-1-0107)
- Deutsche Forschungsgemeinschaft (KR 4512/2-2, GR4334/1-1)
- National Science Foundation (DMS-1829955)
This publication has 39 references indexed in Scilit:
- Improved bound for complexity of matrix multiplicationProceedings of the Royal Society of Edinburgh: Section A Mathematics, 2013
- Improved approximation guarantees for sublinear-time Fourier algorithmsApplied and Computational Harmonic Analysis, 2013
- The cosparse analysis model and algorithmsApplied and Computational Harmonic Analysis, 2013
- Combinatorial Sublinear-Time Fourier AlgorithmsFoundations of Computational Mathematics, 2010
- A note on compressed sensing and the complexity of matrix multiplicationInformation Processing Letters, 2009
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and ImagesSIAM Review, 2009
- The Mailman algorithm: A note on matrix–vector multiplicationInformation Processing Letters, 2009
- $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse RepresentationIEEE Transactions on Signal Processing, 2006
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix MultiplicationSIAM Journal on Computing, 2006
- Spreads, Translation Planes and Kerdock Sets. IISIAM Journal on Algebraic Discrete Methods, 1982