A note on compressed sensing and the complexity of matrix multiplication

DOI10.1016/j.ipl.2009.01.010zbMath1215.68284OpenAlexW2119272727MaRDI QIDQ987795

Craig V. Spencer, Mark A. Iwen

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.01.010

zbMATH Keywords

computational complexityanalysis of algorithmsapproximation algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Approximation algorithms (68W25)

Related Items (5)

Fast Output-Sensitive Matrix Multiplication ⋮ Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps ⋮ Efficiently correcting matrix products ⋮ Detecting the large entries of a sparse covariance matrix in sub-quadratic time ⋮ Unnamed Item

Cites Work

• Matrix multiplication via arithmetic progressions
• Probabilistic counting algorithms for data base applications
• The space complexity of approximating the frequency moments
• Rectangular matrix multiplication revisited
• Geometry and the complexity of matrix multiplication
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Combinatorial Algorithms for Compressed Sensing
• Rapid Multiplication of Rectangular Matrices
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Compressed sensing
• Unnamed Item
• Unnamed Item

This page was built for publication: A note on compressed sensing and the complexity of matrix multiplication