Tuesday, January 04, 2011

CS: Toolbox Sparse Optimization, The Convex Geometry of Linear Inverse Problems, Orthogonal symmetric Toeplitz matrices for CS, Compressed Sensing for Feedback Reduction in MIMO Broadcast Channels

Gabriel Peyre updated his Toolbox Sparse Optmization. The description of the toolbox reads:
This toolbox contains the implementation of what I consider to be fundamental algorithms for non-smooth convex optimization of structured functions. These algorithms might not be the fasted (although they certainly are quite efficient), but they all have a simple implementation in term of black boxes (gradient and proximal mappings, given as callbacks). However, you should have some knowledge about what is a gradient operator and a proximal mapping in order to be able to use this toolbox on your own problems. I suggest you have a look at the "suggested readings" for some more information about all this.
Thanks Gabriel for the heads-up and for this example of Compressed Sensing Recovery using the Douglas-Rachford Algorithm at: http://www.ceremade.dauphine.fr/~peyre/numerical-tour/tours/cs_1_sparse_signal/. The Douglas-Rachford algorithm is described in Proximal Splitting Methods in Signal Processing, Patrick L. Combettes and Jean-Christophe Pesquet.

Today we have three papers, one of which is a generalization of CS and low rank matrix completion issues:.

The Convex Geometry of Linear Inverse Problems by Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, Alan S. Willsky. The abstract reads::
In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered are those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases such as sparse vectors and low-rank matrices, as well as several others including sums of a few permutations matrices, low-rank tensors, orthogonal matrices, and atomic measures. The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery. Thus this work extends the catalog of simple models that can be recovered from limited linear information via tractable convex programming.
Orthogonal symmetric Toeplitz matrices for compressed sensing: Statistical isometry property by Kezhi Li, Lu Gan, Cong Ling. The abstract reads:
Recently, the statistical restricted isometry property (RIP) has been formulated to analyze the performance of deterministic sampling matrices for compressed sensing. In this paper, we propose the usage of orthogonal symmetric Toeplitz matrices (OSTM) for compressed sensing and study their statistical RIP by taking advantage of Stein's method. In particular, we derive the statistical RIP performance bound in terms of the largest value of the sampling matrix and the sparsity level of the input signal. Based on such connections, we show that OSTM can satisfy the statistical RIP for an overwhelming majority of signals with given sparsity level, if a Golay sequence used to generate the OSTM. Such sensing matrices are deterministic, Toeplitz, and efficient to implement. Simulation results show that OSTM can offer reconstruction performance similar to that of random matrices.

We propose a generalized feedback model and compressive sensing based opportunistic feedback schemes for feedback resource reduction in MIMO Broadcast Channels under the assumption that both uplink and downlink channels undergo block Rayleigh fading. Feedback resources are shared and are opportunistically accessed by users who are strong, i.e. users whose channel quality information is above a certain fixed threshold. Strong users send the same feedback information on all shared channels. They are identified by the base station via compressive sensing. Both analog and digital feedbacks are considered. The proposed analog & digital opportunistic feedback schemes are shown to achieve the same sum-rate throughput as that achieved by dedicated feedback schemes, but with feedback channels growing only logarithmically with number of users. Moreover, there is also a reduction in the feedback load. In the analog feedback case, we show that the proposed scheme reduces the feedback noise which eventually results in better throughput, whereas in the digital feedback case the proposed scheme in a noisy scenario achieves almost the throughput obtained in a noiseless dedicated feedback scenario. We also show that for a given fixed budget of feedback bits, there exists a trade-off between the number of shared channels and thresholds accuracy of the fed back SNR.

Credit: Fred Espenak, NASA, Partial Eclipse Today.