Adaptive algorithm for sparse signal recovery

Spike and slab priors play a key role in inducing sparsity for sparse signal recovery. The use of such priors results in hard non-convex and mixed integer programming problems. Most of the existing algorithms to solve the optimization problems involve either simplifying assumptions, relaxations or high computational expenses. We propose a new adaptive alternating direction method of multipliers (AADMM) algorithm to directly solve the presented optimization problem. The algorithm is based on the one-to-one mapping property of the support and non-zero element of the signal. At each step of the algorithm, we update the support by either adding an index to it or removing an index from it and use the alternating direction method of multipliers to recover the signal corresponding to the updated support. Experiments on synthetic data and real-world images show that the proposed AADMM algorithm provides superior performance and is computationally cheaper, compared to the recently developed iterative convex refinement (ICR) algorithm.

Related papers:

title: Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
abstract: This paper demonstrates theoretically and empirically that a greedy algorithm called orthogonal matching pursuit (OMP) can reliably recover a signal with m nonzero entries in dimension d given O(m ln d) random linear measurements of that signal. This is a massive improvement over previous results, which require O(m2) measurements. The new results for OMP are comparable with recent results for another approach called basis pursuit (BP). In some settings, the OMP algorithm is faster and easier to implement, so it is an attractive alternative to BP for signal recovery problems.

title: Compressed sensing
abstract: Suppose x is an unknown vector in Ropfm (a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements n can be dramatically smaller than the size m. Thus, certain natural classes of images with m pixels need only n=O(m1/4log5/2(m)) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual m pixel samples. More specifically, suppose x has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor)-so the coefficients belong to an lscrp ball for 0<ples1. The N most important coefficients in that expansion allow reconstruction with lscr2 error O(N1/2-1p/). It is possible to design n=O(Nlog(m)) nonadaptive measurements allowing reconstruction with accuracy comparable to that attainable with direct knowledge of the N most important coefficients. Moreover, a good approximation to those N important coefficients is extracted from the n measurements by solving a linear program-Basis Pursuit in signal processing. The nonadaptive measurements have the character of "random" linear combinations of basis/frame elements. Our results use the notions of optimal recovery, of n-widths, and information-based complexity. We estimate the Gel'fand n-widths of lscrp balls in high-dimensional Euclidean space in the case 0<ples1, and give a criterion identifying near- optimal subspaces for Gel'fand n-widths. We show that "most" subspaces are near-optimal, and show that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces

title: Sparse Reconstruction by Separable Approximation
abstract: Finding sparse approximate solutions to large underdetermined linear systems of equations is a common problem in signal/image processing and statistics. Basis pursuit, the least absolute shrinkage and selection operator (LASSO), wavelet-based deconvolution and reconstruction, and compressed sensing (CS) are a few well-known areas in which problems of this type appear. One standard approach is to minimize an objective function that includes a quadratic (lscr 2) error term added to a sparsity-inducing (usually lscr1) regularizater. We present an algorithmic framework for the more general problem of minimizing the sum of a smooth convex function and a nonsmooth, possibly nonconvex regularizer. We propose iterative methods in which each step is obtained by solving an optimization subproblem involving a quadratic term with diagonal Hessian (i.e., separable in the unknowns) plus the original sparsity-inducing regularizer; our approach is suitable for cases in which this subproblem can be solved much more rapidly than the original problem. Under mild conditions (namely convexity of the regularizer), we prove convergence of the proposed iterative algorithm to a minimum of the objective function. In addition to solving the standard lscr2-lscr1 case, our framework yields efficient solution techniques for other regularizers, such as an lscrinfin norm and group-separable regularizers. It also generalizes immediately to the case in which the data is complex rather than real. Experiments with CS problems show that our approach is competitive with the fastest known methods for the standard lscr2-lscr1 problem, as well as being efficient on problems with other separable regularization terms.

title: A wavelet-based regularized reconstruction algorithm for SENSE parallel MRI with applications to neuroimaging
abstract: To reduce scanning time and/or improve spatial/temporal resolution in some Magnetic Resonance Imaging (MRI) applications, parallel MRI acquisition techniques with multiple coils acquisition have emerged since the early 1990s as powerful imaging methods that allow a faster acquisition process. In these techniques, the full FOV image has to be reconstructed from the resulting acquired undersampled k-space data. To this end, several reconstruction techniques have been proposed such as the widely-used SENSitivity Encoding (SENSE) method. However, the reconstructed image generally presents artifacts when perturbations occur in both the measured data and the estimated coil sensitivity profiles. In this paper, we aim at achieving accurate image reconstruction under degraded experimental conditions (low magnetic field and high reduction factor), in which neither the SENSE method nor the Tikhonov regularization in the image domain give convincing results. To this end, we present a novel method for SENSE-based reconstruction which proceeds with regularization in the complex wavelet domain by promoting sparsity. The proposed approach relies on a fast algorithm that enables the minimization of regularized non-differentiable criteria including more general penalties than a classical ℓ(1) term. To further enhance the reconstructed image quality, local convex constraints are added to the regularization process. In vivo human brain experiments carried out on Gradient-Echo (GRE) anatomical and Echo Planar Imaging (EPI) functional MRI data at 1.5T indicate that our algorithm provides reconstructed images with reduced artifacts for high reduction factors.

title: Structured sparse priors for image classification
abstract: Model-based compressive sensing (CS) exploits the structure inherent in sparse signals for the design of better signal recovery algorithms. This information about structure is often captured in the form of a prior on the sparse coefficients, the Laplacian being the most common such choice (leading to l1-norm minimization). The recent seminal contribution by Wright et al. exploits the discriminative capability of sparse representations for image classification, specifically face recognition. Their approach employs the analytical framework of CS with class-specific dictionaries. Our contribution is a logical extension of these ideas into structured sparsity for classification. We use class-specific dictionaries in conjunction with discriminative class-specific priors, specifically the spike-and-slab prior widely applied in Bayesian regression. Significantly, the proposed framework takes the burden off the demand for abundant training image samples necessary for the success of sparsity-based classification schemes.

title: Dictionary Learning for Sparse Representation: A Novel Approach
abstract: A dictionary learning problem is a matrix factorization in which the goal is to factorize a training data matrix, Y, as the product of a dictionary, D, and a sparse coefficient matrix, X, as follows, Y ≃ DX. Current dictionary learning algorithms minimize the representation error subject to a constraint on D (usually having unit column-norms) and sparseness of X. The resulting problem is not convex with respect to the pair (D,X). In this letter, we derive a first order series expansion formula for the factorization, DX. The resulting objective function is jointly convex with respect to D and X. We simply solve the resulting problem using alternating minimization and apply some of the previously suggested algorithms onto our new problem. Simulation results on recovery of a known dictionary and dictionary learning for natural image patches show that our new problem considerably improves performance with a little additional computational load.

title: Group structured dirty dictionary learning for classification
abstract: Dictionary learning techniques have gained tremendous success in many classification problems. Inspired by the dirty model for multi-task regression problems, we proposed a novel method called group-structured dirty dictionary learning (GDDL) that incorporates the group structure (for each task) with the dirty model (across tasks) in the dictionary training process. Its benefits are two-fold: 1) the group structure enforces implicitly the label consistency needed between dictionary atoms and training data for classification; and 2) for each class, the dirty model separates the sparse coefficients into ones with shared support and unique support, with the first set being more discriminative. We use proximal operators and block coordinate decent to solve the optimization problem. GDDL has been shown to give state-of-art result on both synthetic simulation and two face recognition datasets.

title: Rapid acquisition of magnetic resonance imaging of the shoulder using three-dimensional fast spin echo sequence with compressed sensing.
abstract: To evaluate the feasibility of 3D fast spin-echo (FSE) imaging with compressed sensing (CS) for the assessment of shoulder.



Twenty-nine patients who underwent shoulder MRI including image sets of axial 3D-FSE sequence without CS and with CS, using an acceleration factor of 1.5, were included. Quantitative assessment was performed by calculating the root mean square error (RMSE) and structural similarity index (SSIM). Two musculoskeletal radiologists compared image quality of 3D-FSE sequences without CS and with CS, and scored the qualitative agreement between sequences, using a five-point scale. Diagnostic agreement for pathologic shoulder lesions between the two sequences was evaluated.



The acquisition time of 3D-FSE MRI was reduced using CS (3min 23s vs. 2min 22s). Quantitative evaluations showed a significant correlation between the two sequences (r=0.872-0.993, p<0.05) and SSIM was in an acceptable range (0.940-0.993; mean±standard deviation, 0.968±0.018). Qualitative image quality showed good to excellent agreement between 3D-FSE images without CS and with CS. Diagnostic agreement for pathologic shoulder lesions between the two sequences was very good (κ=0.915-1).



The 3D-FSE sequence with CS is feasible in evaluating the shoulder joint with reduced scan time compared to 3D-FSE without CS.

title: Adaptive matching pursuit for sparse signal recovery
abstract: Spike and Slab priors have been of much recent interest in signal processing as a means of inducing sparsity in Bayesian inference. Applications domains that benefit from the use of these priors include sparse recovery, regression and classification. It is well-known that solving for the sparse coefficient vector to maximize these priors results in a hard non-convex and mixed integer programming problem. Most existing solutions to this optimization problem either involve simplifying assumptions/relaxations or are computationally expensive. We propose a new greedy and adaptive matching pursuit (AMP) algorithm to directly solve this hard problem. Essentially, in each step of the algorithm, the set of active elements would be updated by either adding or removing one index, whichever results in better improvement. In addition, the intermediate steps of the algorithm are calculated via an inexpensive Cholesky decomposition which makes the algorithm much faster. Results on simulated data sets as well as real-world image recovery challenges confirm the benefits of the proposed AMP, particularly in providing a superior cost-quality trade-off over existing alternatives.

title: Iterative Convex Refinement for Sparse Recovery
abstract: In this letter, we address sparse signal recovery in a Bayesian framework where sparsity is enforced on reconstruction coefficients via probabilistic priors. In particular, we focus on the setup of Yen who employ a variant of spike and slab prior to encourage sparsity. The optimization problem resulting from this model has broad applicability in recovery and regression problems and is known to be a hard non-convex problem whose existing solutions involve simplifying assumptions and/or relaxations. We propose an approach called Iterative Convex Refinement (ICR) that aims to solve the aforementioned optimization problem directly allowing for greater generality in the sparse structure. Essentially, ICR solves a sequence of convex optimization problems such that sequence of solutions converges to a sub-optimal solution of the original hard optimization problem. We propose two versions of our algorithm: a.) an unconstrained version, and b.) with a non-negativity constraint on sparse coefficients, which may be required in some real-world problems. Experimental validation is performed on both synthetic data and for a real-world image recovery problem, which illustrates merits of ICR over state of the art alternatives.

title: A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm
abstract: In this paper, a fast algorithm for overcomplete sparse decomposition, called SL0, is proposed. The algorithm is essentially a method for obtaining sparse solutions of underdetermined systems of linear equations, and its applications include underdetermined sparse component analysis (SCA), atomic decomposition on overcomplete dictionaries, compressed sensing, and decoding real field codes. Contrary to previous methods, which usually solve this problem by minimizing the l 1 norm using linear programming (LP) techniques, our algorithm tries to directly minimize the l 1 norm. It is experimentally shown that the proposed algorithm is about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy.

title: Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
abstract: This paper concerns the performance of the LASSO (also knows as basis pursuit denoising) for recovering sparse signals from undersampled, randomized, noisy measurements. We consider the recovery of the signal $x_o \in \mathbb{R}^N$ from $n$ random and noisy linear observations $y= Ax_o + w$, where $A$ is the measurement matrix and $w$ is the noise. The LASSO estimate is given by the solution to the optimization problem $x_o$ with $\hat{x}_{\lambda} = \arg \min_x \frac{1}{2} \|y-Ax\|_2^2 + \lambda \|x\|_1$. Despite major progress in the theoretical analysis of the LASSO solution, little is known about its behavior as a function of the regularization parameter $\lambda$. In this paper we study two questions in the asymptotic setting (i.e., where $N \rightarrow \infty$, $n \rightarrow \infty$ while the ratio $n/N$ converges to a fixed number in $(0,1)$): (i) How does the size of the active set $\|\hat{x}_\lambda\|_0/N$ behave as a function of $\lambda$, and (ii) How does the mean square error $\|\hat{x}_{\lambda} - x_o\|_2^2/N$ behave as a function of $\lambda$? We then employ these results in a new, reliable algorithm for solving LASSO based on approximate message passing (AMP).

title: Bayesian Compressive Sensing
abstract: The data of interest are assumed to be represented as N-dimensional real vectors, and these vectors are compressible in some linear basis B, implying that the signal can be reconstructed accurately using only a small number M Lt N of basis-function coefficients associated with B. Compressive sensing is a framework whereby one does not measure one of the aforementioned N-dimensional signals directly, but rather a set of related measurements, with the new measurements a linear combination of the original underlying N-dimensional signal. The number of required compressive-sensing measurements is typically much smaller than N, offering the potential to simplify the sensing system. Let f denote the unknown underlying N-dimensional signal, and g a vector of compressive-sensing measurements, then one may approximate f accurately by utilizing knowledge of the (under-determined) linear relationship between f and g, in addition to knowledge of the fact that f is compressible in B. In this paper we employ a Bayesian formalism for estimating the underlying signal f based on compressive-sensing measurements g. The proposed framework has the following properties: i) in addition to estimating the underlying signal f, "error bars" are also estimated, these giving a measure of confidence in the inverted signal; ii) using knowledge of the error bars, a principled means is provided for determining when a sufficient number of compressive-sensing measurements have been performed; iii) this setting lends itself naturally to a framework whereby the compressive sensing measurements are optimized adaptively and hence not determined randomly; and iv) the framework accounts for additive noise in the compressive-sensing measurements and provides an estimate of the noise variance. In this paper we present the underlying theory, an associated algorithm, example results, and provide comparisons to other compressive-sensing inversion algorithms in the literature.

title: Hierarchical Bayesian Sparse Image Reconstruction With Application to MRFM
abstract: This paper presents a hierarchical Bayesian model to reconstruct sparse images when the observations are obtained from linear transformations and corrupted by an additive white Gaussian noise. Our hierarchical Bayes model is well suited to such naturally sparse image applications as it seamlessly accounts for properties such as sparsity and positivity of the image via appropriate Bayes priors. We propose a prior that is based on a weighted mixture of a positive exponential distribution and a mass at zero. The prior has hyperparameters that are tuned automatically by marginalization over the hierarchical Bayesian model. To overcome the complexity of the posterior distribution, a Gibbs sampling strategy is proposed. The Gibbs samples can be used to estimate the image to be recovered, e.g., by maximizing the estimated posterior distribution. In our fully Bayesian approach, the posteriors of all the parameters are available. Thus, our algorithm provides more information than other previously proposed sparse reconstruction methods that only give a point estimate. The performance of the proposed hierarchical Bayesian sparse reconstruction method is illustrated on synthetic data and real data collected from a tobacco virus sample using a prototype MRFM instrument.

title: Sparse Coding From a Bayesian Perspective
abstract: Sparse coding is a promising theme in computer vision. Most of the existing sparse coding methods are based on either <i>l</i><sub>0</sub> or <i>l</i><sub>1</sub> penalty, which often leads to unstable solution or biased estimation. This is because of the nonconvexity and discontinuity of the <i>l</i><sub>0</sub> penalty and the over-penalization on the true large coefficients of the <i>l</i><sub>1</sub> penalty. In this paper, sparse coding is interpreted from a novel Bayesian perspective, which results in a new objective function through maximum a posteriori estimation. The obtained solution of the objective function can generate more stable results than the <i>l</i><sub>0</sub> penalty and smaller reconstruction errors than the <i>l</i><sub>1</sub> penalty. In addition, the convergence property of the proposed algorithm for sparse coding is also established. The experiments on applications in single image super-resolution and visual tracking demonstrate that the proposed method is more effective than other state-of-the-art methods.

title: NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
abstract: Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. This paper applies a smoothing technique and an accelerated first-order algorithm, both from Nesterov , and demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as (1) it is computationally efficient, (2) it is accurate and returns solutions with several correct digits, (3) it is flexible and amenable to many kinds of reconstruction problems, and (4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization and convex programs seeking to minimize the $\ell_1$ norm of $Wx$ under constraints, in which $W$ is not diagonal. The code is available online as a free package in the MATLAB language.

title: Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
abstract: Many problems of recent interest in statistics and machine learning can be posed in the framework of convex optimization. Due to the explosion in size and complexity of modern datasets, it is increasingly important to be able to solve problems with a very large number of features or training examples. As a result, both the decentralized collection or storage of these datasets as well as accompanying distributed solution methods are either necessary or at least highly desirable. In this review, we argue that the alternating direction method of multipliers is well suited to distributed convex optimization, and in particular to large-scale problems arising in statistics, machine learning, and related areas. The method was developed in the 1970s, with roots in the 1950s, and is equivalent or closely related to many other algorithms, such as dual decomposition, the method of multipliers, Douglas–Rachford splitting, Spingarn's method of partial inverses, Dykstra's alternating projections, Bregman iterative algorithms for l1 problems, proximal methods, and others. After briefly surveying the theory and history of the algorithm, we discuss applications to a wide variety of statistical and machine learning problems of recent interest, including the lasso, sparse logistic regression, basis pursuit, covariance selection, support vector machines, and many others. We also discuss general distributed optimization, extensions to the nonconvex setting, and efficient implementation, including some details on distributed MPI and Hadoop MapReduce implementations.

title: Bayesian Variable Selection in Linear Regression
abstract: This article is concerned with the selection of subsets of predictor variables in a linear regression model for the prediction of a dependent variable. It is based on a Bayesian approach, intended to be as objective as possible. A probability distribution is first assigned to the dependent variable through the specification of a family of prior distributions for the unknown parameters in the regression model. The method is not fully Bayesian, however, because the ultimate choice of prior distribution from this family is affected by the data. It is assumed that the predictors represent distinct observables; the corresponding regression coefficients are assigned independent prior distributions. For each regression coefficient subject to deletion from the model, the prior distribution is a mixture of a point mass at 0 and a diffuse uniform distribution elsewhere, that is, a “spike and slab” distribution. The random error component is assigned a normal distribution with mean 0 and standard deviation ...

title: Sparse coding for image denoising using spike and slab prior
abstract: Sparse coding is a challenging and promising theme in image denoising. Its main goal is to learn a sparse representation from an over-complete dictionary. How to obtain a better sparse representation from the dictionary is important for the denoising process. In this paper, starting from the classic image denoising problem, a Bayesian-based sparse coding algorithm is proposed, which learns sparse representation with the spike and slab prior. Using the spike and slab prior, the proposed algorithm can achieve accurate prediction performance and effectively enforce sparsity. Experimental results on image denoising have demonstrated that the proposed algorithm can provide better representation and obtain excellent denoising performance.

title: Multi-task image classification via collaborative, hierarchical spike-and-slab priors
abstract: Promising results have been achieved in image classification problems by exploiting the discriminative power of sparse representations for classification (SRC). Recently, it has been shown that the use of class-specific spike-and-slab priors in conjunction with the class-specific dictionaries from SRC is particularly effective in low training scenarios. As a logical extension, we build on this framework for multitask scenarios, wherein multiple representations of the same physical phenomena are available. We experimentally demonstrate the benefits of mining joint information from different camera views for multi-view face recognition.

title: Bayesian deconvolution of Bernoulli-Gaussian processes
abstract: We present some Bayesian algorithms for the detection and estimation of Bernoulli-Gaussian processes, when just a filtered and noise-corrupted version of the original sequence is available. In a Bayesian framework, reconstruction is obtained from the posterior distribution of this sequence. Then, we conventionally define the likelihood of a Bernoulli-Gaussian process and show that this prior definition allows one to control the errors of detection, as well as the maximum intensity value that can be detected. Some of the traditional algorithms, generally used in image restoration, as MAP, MPM or ICM, are shown to be very efficient for the deconvolution of Bernoulli-Gaussian processes. Simulations and applications to real data are presented.

title: Bayesian Compressive Sensing Using Laplace Priors
abstract: In this paper, we model the components of the compressive sensing (CS) problem, i.e., the signal acquisition process, the unknown signal coefficients and the model parameters for the signal and noise using the Bayesian framework. We utilize a hierarchical form of the Laplace prior to model the sparsity of the unknown signal. We describe the relationship among a number of sparsity priors proposed in the literature, and show the advantages of the proposed model including its high degree of sparsity. Moreover, we show that some of the existing models are special cases of the proposed model. Using our model, we develop a constructive (greedy) algorithm designed for fast reconstruction useful in practical settings. Unlike most existing CS reconstruction methods, the proposed algorithm is fully automated, i.e., the unknown signal coefficients and all necessary parameters are estimated solely from the observation, and, therefore, no user-intervention is needed. Additionally, the proposed algorithm provides estimates of the uncertainty of the reconstructions. We provide experimental results with synthetic 1-D signals and images, and compare with the state-of-the-art CS reconstruction algorithms demonstrating the superior performance of the proposed approach.

title: Sparse Bayesian regularization using Bernoulli-Laplacian priors
abstract: Sparse regularization has been receiving an increasing interest in the literature. Two main difficulties are encountered when performing sparse regularization. The first one is how to fix the parameters involved in the regularization algorithm. The second one is to optimize the inherent cost function that is generally non differentiable, and may also be non-convex if one uses for instance an ℓ0 penalization. In this paper, we handle these two problems jointly and propose a novel algorithm for sparse Bayesian regularization. An interesting property of this algorithm is the possibility of estimating the regularization parameters from the data. Simulation performed with 1D and 2D restoration problems show the very promising potential of the proposed approach. An application to the reconstruction of electroencephalographic signals is finally investigated.

title: A majorization–minimization approach to variable selection using spike and slab priors
abstract: We develop a method to carry out MAP estimation for a class of Bayesian regression models in which coefficients are assigned with Gaussian-based spike and slab priors. The objective function in the corresponding optimization problem has a Lagrangian form in that regression coefficients are regularized by a mixture of squared $l_2$ and $l_0$ norms. A tight approximation to the $l_0$ norm using majorization-minimization techniques is derived, and a coordinate descent algorithm in conjunction with a soft-thresholding scheme is used in searching for the optimizer of the approximate objective. Simulation studies show that the proposed method can lead to more accurate variable selection than other benchmark methods. Theoretical results show that under regular conditions, sign consistency can be established, even when the Irrepresentable Condition is violated. Results on posterior model consistency and estimation consistency, and an extension to parameter estimation in the generalized linear models are provided.

title: Regression Shrinkage and Selection via the Lasso
abstract: We propose a new method for estimation in linear models. The 'lasso' minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant. Because of the nature of this constraint it tends to produce some coefficients that are exactly 0 and hence gives interpretable models. Our simulation studies suggest that the lasso enjoys some of the favourable properties of both subset selection and ridge regression. It produces interpretable models like subset selection and exhibits the stability of ridge regression. There is also an interesting relationship with recent work in adaptive function estimation by Donoho and Johnstone. The lasso idea is quite general and can be applied in a variety of statistical models: extensions to generalized regression models and tree-based models are briefly described.

title: Adaptive Sparsity Matching Pursuit Algorithm for Sparse Reconstruction
abstract: This letter presents a new greedy method, called Adaptive Sparsity Matching Pursuit (ASMP), for sparse solutions of underdetermined systems with a typical/random projection matrix. Unlike anterior greedy algorithms, ASMP can extract information on sparsity of the target signal adaptively with a well-designed stagewise approach. Moreover, it takes advantage of backtracking to refine the chosen supports and the current approximation in the process. With these improvements, ASMP provides even more attractive results than the state-of-the-art greedy algorithm CoSaMP without prior knowledge of the sparsity level. Experiments validate the proposed algorithm works well for both noiseless signals and noisy signals, with the recovery quality often outperforming that of l1-minimization and other greedy algorithms.

title: A parallel scheme for the forward/backward substitutions in solving sparse linear equations
abstract: A parallel processing scheme for the solution of sparse linear network equations is presented. The scheme assumes an already factorized coefficient matrix and decomposes the forward/backward substitution operation into independent sequences. In doing this, sparse vector methods are used and the full right-hand side vector is considered as a sum of several sparse vectors. The developed scheme is simulated for various test systems, and the calculated gains in computation times are given. The results obtained are pertinent to the analysis of power-system problems.

title: Parallel algorithm and hybrid regularization for dynamic PET reconstruction
abstract: To improve the estimation at the voxel level in dynamic Positron Emission Tomography (PET) imaging, we propose to develop a convex optimization approach based on a recently proposed parallel proximal method (PPXA). This class of algorithms was successfully employed for 2D deconvolution in the presence of Poisson noise and it is extended here to (dynamic) space + time PET image reconstruction. Hybrid regularization defined as a sum of a total variation and a sparsity measure is considered in this paper. The total variation is applied to each temporal-frame and a wavelet regularization is considered for the space+time data. Total variation allows us to smooth the wavelet artifacts introduced when the wavelet regularization is used alone. The proposed algorithm was evaluated on simulated dynamic fluorodeoxyglucose (FDG) brain data and compared with a regularized Expectation Maximization (EM) reconstruction. From the reconstructed dynamic images, parametric maps of the cerebral metabolic rate of glucose (CMRglu) were computed. Our approach shows a better reconstruction at the voxel level.

title: Spike and Slab Variational Inference for Multi-Task and Multiple Kernel Learning
abstract: We introduce a variational Bayesian inference algorithm which can be widely applied to sparse linear models. The algorithm is based on the spike and slab prior which, from a Bayesian perspective, is the golden standard for sparse inference. We apply the method to a general multi-task and multiple kernel learning model in which a common set of Gaussian process functions is linearly combined with task-specific sparse weights, thus inducing relation between tasks. This model unifies several sparse linear models, such as generalized linear models, sparse factor analysis and matrix factorization with missing values, so that the variational algorithm can be applied to all these cases. We demonstrate our approach in multi-output Gaussian process regression, multi-class classification, image processing applications and collaborative filtering.

title: Learning with Compressible Priors
abstract: We describe a set of probability distributions, dubbed compressible priors, whose independent and identically distributed (iid) realizations result in p-compressible signals. A signal x ∈ ℝN is called p-compressible with magnitude R if its sorted coefficients exhibit a power-law decay as |x|(i) ≲ R · i-d, where the decay rate d is equal to 1/p. p-compressible signals live close to K-sparse signals (K ≪ N) in the lr-norm (r > p) since their best K-sparse approximation error decreases with O (R · K1/r-1/p). We show that the membership of generalized Pareto, Student's t, log-normal, Frechet, and log-logistic distributions to the set of compressible priors depends only on the distribution parameters and is independent of N. In contrast, we demonstrate that the membership of the generalized Gaussian distribution (GGD) depends both on the signal dimension and the GGD parameters: the expected decay rate of N-sample iid realizations from the GGD with the shape parameter q is given by 1/ [qlog (N/q)]. As stylized examples, we show via experiments that the wavelet coefficients of natural images are 1.67-compressible whereas their pixel gradients are 0.95 log (N/0.95)-compressible, on the average. We also leverage the connections between compressible priors and sparse signals to develop new iterative re-weighted sparse signal recovery algorithms that outperform the standard l1-norm minimization. Finally, we describe how to learn the hyperparameters of compressible priors in underdetermined regression problems by exploiting the geometry of their order statistics during signal recovery.

title: A sparse signal reconstruction perspective for source localization with sensor arrays
abstract: We present a source localization method based on a sparse representation of sensor measurements with an overcomplete basis composed of samples from the array manifold. We enforce sparsity by imposing penalties based on the /spl lscr//sub 1/-norm. A number of recent theoretical results on sparsifying properties of /spl lscr//sub 1/ penalties justify this choice. Explicitly enforcing the sparsity of the representation is motivated by a desire to obtain a sharp estimate of the spatial spectrum that exhibits super-resolution. We propose to use the singular value decomposition (SVD) of the data matrix to summarize multiple time or frequency samples. Our formulation leads to an optimization problem, which we solve efficiently in a second-order cone (SOC) programming framework by an interior point implementation. We propose a grid refinement method to mitigate the effects of limiting estimates to a grid of spatial locations and introduce an automatic selection criterion for the regularization parameter involved in our approach. We demonstrate the effectiveness of the method on simulated data by plots of spatial spectra and by comparing the estimator variance to the Crame/spl acute/r-Rao bound (CRB). We observe that our approach has a number of advantages over other source localization techniques, including increased resolution, improved robustness to noise, limitations in data quantity, and correlation of the sources, as well as not requiring an accurate initialization.

title: Expectation propagation in linear regression models with spike-and-slab priors
abstract: An expectation propagation (EP) algorithm is proposed for approximate inference in linear regression models with spike-and-slab priors. This EP method is applied to regression tasks in which the number of training instances is small and the number of dimensions of the feature space is large. The problems analyzed include the reconstruction of genetic networks, the recovery of sparse signals, the prediction of user sentiment from customer-written reviews and the analysis of biscuit dough constituents from NIR spectra. The proposed EP method outperforms in most of these tasks another EP method that ignores correlations in the posterior and a variational Bayes technique for approximate inference. Additionally, the solutions generated by EP are very close to those given by Gibbs sampling, which can be taken as the gold standard but can be much more computationally expensive. In the tasks analyzed, spike-and-slab priors generally outperform other sparsifying priors, such as Laplace, Student’s $$ and horseshoe priors. The key to the improved predictions with respect to Laplace and Student’s $$ priors is the superior selective shrinkage capacity of the spike-and-slab prior distribution.

title: The Variational Garrote
abstract: We analyze the variational method for sparse regression using ℓ0 regularization. The variational approximation results in a model that is similar to Breiman’s Garrote model. We refer to this method as the Variational Garrote (VG). The VG has the effect of making the problem effectively of maximal rank even when the number of samples is small compared to the number of variables. We propose a naive mean field approximation combined with a maximum a posteriori (MAP) approach to estimate the model parameters and use an annealing and reheating schedule of the sparsity hyper-parameter to avoid local minima. The hyper-parameter is set by cross-validation. We compare the VG with the lasso, ridge regression and the recently introduced Bayesian paired mean field method (PMF) (Titsias and Lázaro-Gredilla in Advances in neural information processing systems, vol. 24, pp. 2339–2347, 2011). For fair comparison, we implemented a similar annealing-reheating schedule for the PMF sparsity parameter. Numerical results show that the VG and PMF yield more accurate predictions and more accurately reconstruct the true model than the other methods. The VG finds correct solutions when the lasso solution is inconsistent due to large input correlations. In the experiments that we consider we find that the VG, although based on a simpler approximation than the PMF, yields qualitatively similar or better results and is computationally more efficient. The naive implementation of the VG scales cubic with the number of features. By introducing Lagrange multipliers we obtain a dual formulation of the problem that scales cubic in the number of samples, but close to linear in the number of features.

title: A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
abstract: We consider the class of iterative shrinkage-thresholding algorithms (ISTA) for solving linear inverse problems arising in signal/image processing. This class of methods, which can be viewed as an extension of the classical gradient algorithm, is attractive due to its simplicity and thus is adequate for solving large-scale problems even with dense matrix data. However, such methods are also known to converge quite slowly. In this paper we present a new fast iterative shrinkage-thresholding algorithm (FISTA) which preserves the computational simplicity of ISTA but with a global rate of convergence which is proven to be significantly better, both theoretically and practically. Initial promising numerical results for wavelet-based image deblurring demonstrate the capabilities of FISTA which is shown to be faster than ISTA by several orders of magnitude.

title: Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm
abstract: We present a nonparametric algorithm for finding localized energy solutions from limited data. The problem we address is underdetermined, and no prior knowledge of the shape of the region on which the solution is nonzero is assumed. Termed the FOcal Underdetermined System Solver (FOCUSS), the algorithm has two integral parts: a low-resolution initial estimate of the real signal and the iteration process that refines the initial estimate to the final localized energy solution. The iterations are based on weighted norm minimization of the dependent variable with the weights being a function of the preceding iterative solutions. The algorithm is presented as a general estimation tool usable across different applications. A detailed analysis laying the theoretical foundation for the algorithm is given and includes proofs of global and local convergence and a derivation of the rate of convergence. A view of the algorithm as a novel optimization method which combines desirable characteristics of both classical optimization and learning-based algorithms is provided. Mathematical results on conditions for uniqueness of sparse solutions are also given. Applications of the algorithm are illustrated on problems in direction-of-arrival (DOA) estimation and neuromagnetic imaging.