The need of reconstructing discrete-valued sparse signals from few measurements, that is solving an undetermined system of linear equations, appears frequently in science and engineering. Those signals appear, for example, in error correcting codes as well as massive Multiple-Input Multiple-Output (MIMO) channel and wideband spectrum sensing. A particular example is given by wireless communications, where the transmitted signals are sequences of bits, i.e., with entries in f0; 1g. Whereas classical compressed sensing algorithms do not incorporate the additional knowledge of the discrete nature of the signal, classical lattice decoding approaches do not utilize sparsity constraints. In this talk, we present an approach that incorporates a discrete values prior into basis pursuit. In particular, we address finite-valued sparse signals, i.e., sparse signals with entries in a finite alphabet. We will introduce an equivalent null space characterization and show that phase transition takes place earlier than when using the classical basis pursuit approach. We will further discuss robustness of the algorithm and show that the nonnegative case is very different from the bipolar one. One of our findings is that the positioning of the zero in the alphabet - i.e., whether it is a boundary element or not - is crucial.
The novel framework of parabolic molecules provides for the first time a unifying framework for (sparse) approximation properties of directional representation systems by, in particular, including curvelets and shearlets.
However, the considered common bracket is parabolic scaling, which excludes systems such as ridgelets and wavelets. In this paper, we therefore provide a generalization of this framework, which we coin α-molecules, by introducing an additional parameter α, which specifies the extent of anisotropy in the scaling. We show that, for instance, both ridgelets and wavelets are in fact α-molecules. As an application of the concept, we then analyze the sparse approximation behavior of α-molecules. Utilizing the idea of sparsity equivalence, it is possible to identify large classes of α-molecules providing the same sparse approximation behavior.