A note on compressed sensing and the complexity of matrix multiplication

DOI10.1016/J.IPL.2009.01.010zbMATH Open1215.68284OpenAlexW2119272727MaRDI QIDQ987795FDOQ987795

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

Recommendations

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

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)

Cites Work

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

Cited In (5)

• Sketching with Kerdock's Crayons: Fast Sparsifying Transforms for Arbitrary Linear Maps
• Title not available (Why is that?)
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Efficiently correcting matrix products
• Fast Output-Sensitive Matrix Multiplication

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)