Xavier Andrade edited sectionIntroduction_.tex  almost 10 years ago

Commit id: 2698d044c8b57171f4f37c3987c35e577a3e4fda

deletions | additions      

       

Matrices are one of the most fundamental objects in the mathematical description of nature, and as such they are ubiquitous in every area of science. For example, they arise naturally in all types of linear response theories as the first term in a multidimensional Taylor series, encoding the response of each component of the system to each component of the stimulus. Hence, in many scientific applications, matrices contain the essential information about the system being studied.  The Despite their ubiquity, the  calculation of matrices often requires considerable computational effort. Returning to the linear response theory example, it might be necessary to individually calculate the response of every component of the system to every component of the stimulus and, depending on the area of application, each individual computation may itself be quite expensive. The overall expense stems from the fact that evaluating a matrix of dimension \(N\times M\) requires, in principle, the individual evaluation of \(N\times M\) elements. But this does not always have to be the case. For example, if we know \emph{a priori} the eigenvectors of a \(N\times N\) diagonalizable matrix, then we can obtain the full matrix by only calculating the \(N\) diagonal elements. Similarly, a sparse matrix, which contains many zero elements, can be evaluated by calculating only the non-zero elements, if we know in advance where such elements are located. 

approach~\cite{Candes2006,Donoho2006,Candes2008}. Compressed sensing  is 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 expermiental applications~\cite{Gross_2010,Zhu_2012,Sanders2012,Doneva_2010}. However compressed sensing is also becoming a tool for theoretical applications \cite{Schaeffer_2013,Almeida_2012}  In previous work, we showed that compressed sensing can also be used to reduce the amount of computation in numerical  simulations~\cite{Andrade2012b}, the reconstruction of experimental  spectra~\cite{Sanders2012}, and the atomistic modeling of open quantum  systems~\cite{Markovich2013}. simulations~\cite{Andrade2012b}.  In this article, we extend compressed sensing to the problem of constructing matrices. {\color{red}(Perhaps  add sentence about other CS applications which are not our own.)}