Distributed algorithms for basis pursuit (also here) by João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, Markus Püscheldd. The abstract reads:
The Basis Pursuit (BP) problem consists in finding a least l1 norm solution of the underdetermined linear system Ax = b. It arises in many areas of electrical engineering and applied mathematics. Applications include signal compression and modeling, estimation, fitting, and compressed sensing. In this paper, we explore methods for solving the BP in a distributed environment, i.e., when the computational resources and the matrix A are distributed over several interconnected nodes. Special instances of this distributed framework include sensor networks and distributed memory and/or processor platforms. We consider two distribution paradigms: either the columns or the rows of A are distributed across the nodes. The several algorithms that we present impose distinct requirements on the degree of connectivity of the network and the per-node computational complexity.
Compressed sensing for radio interferometry : prior-enhanced Basis Pursuit imaging techniques by Yves Wiaux, Laurent Jacques, Gilles Puy, Anna Scaife, Pierre Vandergheynst. The abstract reads:
We propose and assess the performance of new imaging techniques for radio interferometry that rely on the versatility of the compressed sensing framework to account for prior information on the signals. The present manuscript represents a summary of recent work.
Stability of l1 minimisation in compressed sensing by Przemyslaw Wojtaszczyk. The abstract reads:A variety of practical methods have recently been introduced for finding maximally sparse representations from overcomplete dictionaries, a central computational task in compressed sensing and source localization applications as well as numerous others. Many of the underlying algorithms rely on iterative reweighting schemes that produce more focal estimates as optimization progresses. Two such variants are iterative reweighted l1 and l2 minimization; however, some properties related to convergence and sparse estimation, as well as possible generalizations, are still not clearly understood or fully exploited. In this paper, we make the distinction between separable and nonseparable iterative reweighting algorithms. The vast majority of existing methods are separable, meaning the weighting of a given coefficient at each iteration is only a function of that individual coefficient from the previous iteration (as opposed to dependency on all coefficients). We examine two such separable reweighting schemes: an l2 method from Chartand and Yin (2008) and an l1 approach from Cand`es et al. (2008), elaborating on convergence results and explicit connections between them. We then explore an interesting non-separable variant that can be implemented via either l2 or l1 reweighting and show several desirable properties relevant to sparse recovery. For the former, we show a direct connection with Chartrand and Yin's approach. For the latter, we demonstrate two desirable properties: (i) each iteration can only improve the sparsity and (ii), for any dictionary and sparsity profile, there will always exist cases where non-separable l1 reweighting improves over standard l1 minimization.
Recovery of Non-Negative Signals from Compressively Sampled Observations Via Non-Negative Quadratic Programming by Paul O’Grady and Scott Rickard . The abstract reads:We discuss known results (c.f. [16, 6]) about stability of l1 minimisation (denoted \Delta_1) with respect to the measurement error and how those results depend on the measurement matrix \Phi. Then we produce a large class of measurement matrices \Phi for which we can apply results from [16] so we have estimate
\Delta_1(\Phi(x) + r) − x_2 \le C(r_2 + k^(−1/2) \sigma^1_k(x)). (1)
We conclude with a modification of l1 minimisation which gives (1) for most random measurement matrices considered in compressed sensing literature. We also discuss stability of instance optimality in probability.
The new emerging theory of Compressive Sampling has demonstrated that by exploiting the structure of a signal, it is possible to sample a signal below the Nyquist rate and achieve perfect reconstruction. In this paper, we consider a special case of Compressive Sampling where the uncompressed signal is non-negative, and propose an extension of Non-negative Quadratic Programming - which utilises Iteratively Reweighted Least Squares - for the recovery of non-negative minimum lp-norm solutions, 0 \le p \le 1. Furthermore, we investigate signal recovery performance where the sampling matrix has entries drawn from a Gaussian distribution with decreasing number of negative values, and demonstrate that - unlike standard Compressive Sampling - the standard Gaussian distribution is unsuitable for this special case.
