Universal Compressed Sensing of Markov Sources
The main promise of compressed sensing is accurate recovery f high-dimensional structured signals from an underdetermined set of randomized linear projections. Sev eral types of structure such as sparsity and low-rankness have already been explored in the literature. For each type o f structure, a recovery algorithm has been developed based on the properties of signals with that type of structur e. Such algorithms recover any signal complying with the assumed model from its sufficient number of linear projectio ns. However, in many practical situations the underlying structure of the signal is not known, or is only partially kno wn. Moreover, it is desirable to have recovery algorithms that can be applied to signals with different types of struct ure. In this paper, the problem of developing “universal” algori thms for compressed sensing of stochastic processes is studied. First, Rényi’s notion of information dimension i s generalized to analog stationary processes. This provide s a measure of complexity for such processes and is connected t o the number of measurements required for their accurate recovery. Then a minimum entropy pursuit (MEP) alg orithm is proposed, and it is proven that it can reliably and robustly recover any Markov process of any order from suf ficient number of randomized linear measurements, without having any prior information about the distributio n f the process. An implementable version of MEP with the same performance guarantees is also provided. I. I NTRODUCTION Consider the fundamental problem of compressed sensing (CS ): a signalxo ∈ R is observed through a data acquisition system that can be modeled as a linear projectio n systemy o = Ax n o , whereA ∈ Rm×n denotes the measurement matrix. The decoder is interested in recoverin g the signalxo from the measurements y m o . In CS we are usually interested in the case where xo is high-dimensional and the number of measurements m i much smaller than the ambient dimension of the signal, i.e., m ≪ n. In such a setup, clearly, without any extra information, it is impossible to recover xo from y m o , and the system of linear equations described by y m o = Ax n has infinitely many solutions. However, if some extra information about the str ucture ofxo is available, for instance it is known that xo is sparse, i.e., ‖xo‖0 ≪ n, then it is known that this additional information can be exp loited andxo can be recovered fromy o . For sparse signals, it can be proved that in fact the signal r ecovery can be achieved efficiently and robustly [1]–[3]. This result can be extended to several other structures as well [4]–[11]. In each of these cases, the signal is known to have some specific structure, and the de coder takes advantage of its knowledge about the structure of the signal to recover it from its linear project ions.