Xavier Andrade edited Compressibility.tex  over 9 years ago

Commit id: 56c5c00edeccdb4c945e3eaff4b5ef64209b9f9c

deletions | additions      

       

What makes looking for sparsifying basis attractive, even at some computational cost and code-complexity overhead, are the properties of the recovery method (detailed in the next section). First, the cost of recovering the matrix is roughly proportional to its sparsity. Second, the reconstruction of the matrix is always exact up to a desired precision; even if the sparsifying basis is not a good one, we eventually obtain the correct result. The penalty for a bad sparsifying basis is additional computations, which in the worst case make the calculation as costly as if compressed sensing were not used at all. This feature implies that the method will almost certainly offer some performance gain.  There is an important consideration to make. For some matrices there is a preferred basis where the matrix is cheaper to compute, to compute it in a different basis might offset the reduction in cost offered by compressed sensing.  %There are serveral peculiarities to our approach. While in general the additional knowledge %about the problem must be integrated a priori while designing the simulation strategy, our %approach is general and can  %The properties of the method: no need to know the location of the non-zero elements, quasi%-linear scaling with the matrix sparsity and exact recovery, make it practical to use