A note on compressed sensing and the complexity of matrix multiplication

DOI10.1016/J.IPL.2009.01.010MaRDI QIDQ987795zbMATHOpenAlexFDO

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)