Sparsity-Based Recovery of Finite Alphabet Solutions to Underdetermined Linear Systems

We consider the problem of estimating a deterministic finite alphabet vector f from underdetermined measurements y = A f , where A is a given (random) n × N matrix. Two new convex optimization methods are introduced for the recovery of finite alphabet signals via ℓ₁-norm minimization. The first method is based on regularization. In the second approach, the problem is formulated as the recovery of sparse signals after a suitable sparse transform. The regularization-based method is less complex than the transform-based one. When the alphabet size p equals 2 and (n, N) grows proportionally, the conditions under which the signal will be recovered with high probability are the same for the two methods. When p > 2, the behavior of the transform-based method is established. Experimental results support this theoretical result and show that the transform method outperforms the regularization-based one.