A note on compressed sensing and the complexity of matrix multiplication |
| |
| Authors: | M.A. Iwen C.V. Spencer |
| |
| Affiliation: | a Institute for Mathematics and its Applications, University of Minnesota, 400 Lind Hall, 207 Church Street S.E., Minneapolis, MN 55455, USA
b Institute for Advanced Study, School of Mathematics, 1 Einstein Drive, Princeton, NJ 08540, USA |
| |
| Abstract: | We consider the conjectured O(N2+?) time complexity of multiplying any two N×N matrices A and B. Our main result is a deterministic Compressed Sensing (CS) algorithm that both rapidly and accurately computes A⋅B provided that the resulting matrix product is sparse/compressible. As a consequence of our main result we increase the class of matrices A, for any given N×N matrix B, which allows the exact computation of A⋅B to be carried out using the conjectured O(N2+?) operations. Additionally, in the process of developing our matrix multiplication procedure, we present a modified version of Indyk's recently proposed extractor-based CS algorithm [P. Indyk, Explicit constructions for compressed sensing of sparse signals, in: SODA, 2008] which is resilient to noise. |
| |
| Keywords: | Algorithms Analysis of algorithms Approximation algorithms Computational complexity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
