An information theoretic approach to sparse representation and recovery of signals

Abstract

Compressed sensing, also known as compressed sampling, is a scheme that embeds the newlineintelligence of compression along with signal acquisition in discrete form. The central theme newlineof compressed sampling is built around a scheme that identifies the sparsest solution of newlinea severely under-determined consistent system of linear equations. This observation calls newlinefor new strategies of signal recovery which would work with unusually small number of newlinemeasurements, especially in the presence of noise. newlineThe efficiency of a signal acquisition system that uses compressed sensing depends on newlinethree aspects: newline1. A basis for the sparse representation of the signal of interest. newline2. A measurement matrix that captures maximum information of the signal in a reduced newlineset of measurements. newline3. A method that recovers the sparse representation with high probability such as to newlinereconstruct the signal without degrading the quality. newlineSampling at sub-Nyquist rate uses random measurement matrices as they have low newlinemutual coherence with any sparse representation basis. The compressed measurements thus newlineobtained support perfect recovery with high probability if the number of measurements M is newlineat least of the order of Klog(N/K), where K is the sparsity of the signal x and#8712; R newline newlineN, measured in newlineterms of its l0 count. Since the minimization of the l0 count is NP hard, other algorithms newlinewhich minimize the l1-norm or non-linear greedy algorithms assume practical importance. newlineThe l1-norm minimization recovers the optimal solution under certain conditions but is newlinecomputationally complex. A majority of the greedy recovery algorithms depends on residual newlineenergy minimization which restricts the robustness of the recovery in the presence of noise. newlineThis work proposes an information-theoretic approach to sparse representation and newlinerecovery of signals, which is robust under noisy environments. newline