A note on compressed sensing and the complexity of matrix multiplication

DOI10.1016/J.IPL.2009.01.010MaRDI QIDQ987795zbMATH OpenOpenAlexFDO

Authors M. A. Iwen, C. V. Spencer

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

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

Recommendations

• Compressed matrix multiplication
• Compressed matrix multiplication
• Algorithms – ESA 2004
• Fast sparse matrix multiplication
• Fast Output-Sensitive Matrix Multiplication

Cites work

• scientific article; zbMATH DE number 5764870 (Why is no real title available?)
• scientific article; zbMATH DE number 5764871 (Why is no real title available?)
• Combinatorial Algorithms for Compressed Sensing
• Compressed sensing
• Geometry and the complexity of matrix multiplication
• Matrix multiplication via arithmetic progressions
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Probabilistic counting algorithms for data base applications
• Rapid Multiplication of Rectangular Matrices
• Rectangular matrix multiplication revisited
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• The space complexity of approximating the frequency moments

Cited in

(6)

• Improving compressed matrix multiplication using control variate method
• Fast Output-Sensitive Matrix Multiplication
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Efficiently correcting matrix products
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987795)