Xavier Andrade edited Introduction.tex  over 9 years ago

Commit id: 082959ffa9c66419bbbd30be51c666e51c12d9d4

deletions | additions      

       

The key numerical procedure of our approach is a method to cheaply recover sparse matrices with a cost that is essentially proportional to the number of non-zero elements. The matrix reconstruction procedure is based on the increasingly popular compressed sensing  approach~\cite{Candes2006,Donoho2006,Candes2008}, a state-of-the-art signal processing technique developed for minimizing the amount of data that needs to be measured to reconstruct a sparse signal.  The use of compressed sensing and sparse sampling methods for scientific development has been dominated by experimental applications~\cite{Kazimierczuk_2011,Holland_2011,Gross_2010,Zhu_2012,Sanders2012,Doneva_2010}. applications~\cite{Doneva_2010,Gross_2010,Kazimierczuk_2011,Holland_2011,Zhu_2012,Sanders2012}.  However compressed sensing is also becoming a tool for theoretical applications~\cite{Schaeffer_2013,Almeida_2012,Nelson_2013}. applications~\cite{Andrade2012b,Almeida_2012,Schaeffer_2013,Nelson_2013}.  In particular, in previous work we have shown that compressed sensing can also be used to reduce the amount of computation in numerical simulations~\cite{Andrade2012b}. In this article, we apply compressed sensing to the problem of computing matrices. This method has two key properties. First, the cost of the procedure is quasi-linear with the size of the number of non-zero elements in the matrix, without the need to know \emph{a priori} the location of the non-zero elements. Second, the rescontruction is exact. Furthermore, such a method is useful not only for sparse matrices. It makes it practical to devise methods to find a basis where the matrix is known or suspected to be sparse, based on the characteristics and previous knowledge of each problem.