Compressed sensing with structured sparsity and structured acquisition

Compressed Sensing (CS) is an appealing framework for applications such as Magnetic Resonance Imaging (MRI). However, up-to-date, the sensing schemes suggested by CS theories are made of random isolated measurements, which are usually incompatible with the physics of acquisition. To reflect the physical constraints of the imaging device, we introduce the notion of blocks of measurements: the sensing scheme is not a set of isolated measurements anymore, but a set of groups of measurements which may represent any arbitrary shape (parallel or radial lines for instance). Structured acquisition with blocks of measurements are easy to implement, and provide good reconstruction results in practice. However, very few results exist on the theoretical guarantees of CS reconstructions in this setting. In this paper, we derive new CS results for structured acquisitions and signals satisfying a prior structured sparsity. The obtained results provide a recovery probability of sparse vectors that explicitly depends on their support. Our results are thus support-dependent and offer the possibility for flexible assumptions on the sparsity structure. Moreover, the results are drawing-dependent, since we highlight an explicit dependency between the probability of reconstructing a sparse vector and the way of choosing the blocks of measurements. Numerical simulations show that the proposed theory is faithful to experimental observations.     

Learning Semidefinite Regularizers

Foundations of Computational Mathematics - Regularization techniques are widely employed in optimization-based approaches for solving ill-posed inverse problems in data analysis and scientific...     

A note on the representation of positive polynomials with structured sparsity

We consider real polynomials in finitely many variables. Let the variables consist of finitely many blocks that are allowed to overlap in a certain way. Let the solution set of a finite system of polynomial inequalities be given, where each inequality involves only variables of one block. We investigate polynomials that are positive on such a set and sparse in the sense that each monomial involves only variables of one block. In particular, we derive a short and direct proof for Lasserre’s theorem on the existence of sums of squares certificates respecting the block structure. The motivation for the results can be found in the literature on numerical methods for global optimization of polynomials that exploit sparsity. The first and the third author were supported by the DFG grant “Barrieren”. The second author was supported by “Studienstiftung des deutschen Volkes”.     

Beyond sparsity: Recovering structured representations by ${\ell}^1$ minimization and greedy algorithms

Finding a sparse approximation of a signal from an arbitrary dictionary is a very useful tool to solve many problems in signal processing. Several algorithms, such as Basis Pursuit (BP) and Matching Pursuits (MP, also known as greedy algorithms), have been introduced to compute sparse approximations of signals, but such algorithms a priori only provide sub-optimal solutions. In general, it is difficult to estimate how close a computed solution is from the optimal one. In a series of recent results, several authors have shown that both BP and MP can successfully recover a sparse representation of a signal provided that it is sparse enough, that is to say if its support (which indicates where are located the nonzero coefficients) is of sufficiently small size. In this paper we define identifiable structures that support signals that can be recovered exactly by minimization (Basis Pursuit) and greedy algorithms. In other words, if the support of a representation belongs to an identifiable structure, then the representation will be recovered by BP and MP. In addition, we obtain that if the output of an arbitrary decomposition algorithm is supported on an identifiable structure, then one can be sure that the representation is optimal within the class of signals supported by the structure. As an application of the theoretical results, we give a detailed study of a family of multichannel dictionaries with a special structure (corresponding to the representation problem ) often used in, e.g., under-determined source sepa-ration problems or in multichannel signal processing. An identifiable structure for such dictionaries is defined using a generalization of Tropp’s Babel function which combines the coherence of the mixing matrix with that of the time-domain dictionary , and we obtain explicit structure conditions which ensure that both minimization and a multi-channel variant of Matching Pursuit can recover structured multichannel representations. The multichannel Matching Pursuit algorithm is described in detail and we conclude with a discussion of some implications of our results in terms of blind source separation based on sparse decompositions. Communicated by Yuesheng Xu     

Separation dimension and sparsity

The separation dimension of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family of total orders of , such that for any two disjoint edges of G, there exists at least one total order in in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge‐density of a graph on one another. On one hand, we show that the maximum separation dimension of a k‐degenerate graph on n vertices is and that there exists a family of 2‐degenerate graphs with separation dimension . On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n‐vertex graphs with separation dimension s have at most edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound.     

Bicomplex signals with sparsity constraints

In this paper, we aim to prove the possibility to reconstruct a bicomplex sparse signal, with high probability, from a reduced number of bicomplex random samples. Due to the idempotent representation of the bicomplex algebra, this case is similar to the case of the standard Fourier basis, thus allowing us to adapt in a rather easy way the arguments from the recent works of Rauhut and Candés et al.     

Iterated hard-thresholding for linear inverse problems with sparsity constraints

We describe an iterative algorithm for the minimization of Tikhonov type functionals which involve sparsity constraints in form of ℓ^p -penalties which have been proposed recently for the regularization of ill-posed problems. In contrast to the well-known algorithm considered by Daubechies, Defrise and De Mol, it uses hard instead of soft thresholding. This hard thresholding algorithm is based on the generalized conditional gradient method. General results on the convergence of the generalized conditional gradient method enable us to prove strong convergence of the iterates. Furthermore we are able to establish convergence rates of O (n^–1/2) and O (λⁿ) for p = 1 and 1 < p ≤ 2 respectively. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A sparsity preserving stochastic gradient methods for sparse regression

We propose a new stochastic first-order algorithm for solving sparse regression problems. In each iteration, our algorithm utilizes a stochastic oracle of the subgradient of the objective function. Our algorithm is based on a stochastic version of the estimate sequence technique introduced by Nesterov (Introductory lectures on convex optimization: a basic course, Kluwer, Amsterdam, 2003). The convergence rate of our algorithm depends continuously on the noise level of the gradient. In particular, in the limiting case of noiseless gradient, the convergence rate of our algorithm is the same as that of optimal deterministic gradient algorithms. We also establish some large deviation properties of our algorithm. Unlike existing stochastic gradient methods with optimal convergence rates, our algorithm has the advantage of readily enforcing sparsity at all iterations, which is a critical property for applications of sparse regressions.     

Exploiting sparsity in primal-dual interior-point methods for semidefinite programming

The Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro and Nesterov-Todd search directions have been used in many primal-dual interior-point methods for semidefinite programs. This paper proposes an efficient method for computing the two directions when the semidefinite program to be solved is large scale and sparse.     

Recognizing underlying sparsity in optimization

Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding to the vector of variables. A combinatorial optimization problem is then formulated to increase the number of zeros of the Hessian matrices in the resulting transformed space, and a heuristic greedy algorithm is applied to this formulation. The resulting method can thus be viewed as a preprocessor for converting a problem with hidden sparsity into one in which sparsity is explicit. When it is combined with the sparse semidefinite programming relaxation by Waki et al. for polynomial optimization problems, the proposed method is shown to extend the performance and applicability of this relaxation technique. Preliminary numerical results are presented to illustrate this claim. S. Kim’s research was supported by Kosef R01-2005-000-10271-0. M. Kojima’s research was supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

Data structures to vectorize CG algorithms for general sparsity patterns

We describe an implementation of Conjugate Gradient-type iterative algorithms for problems with general sparsity patterns on a vector processor with a hierarchy of memories, such as the IBM 3090/VF. The implementation relies on the wavefront approach to vectorize the solution of the two sparse triangular systems that arise when using ILU type preconditioners. The data structure is the key to an effective implementation of sparse computational kernels on a vector processor. A data structure is a combination of a layout of the matrix coefficients and ordering schemes for the vectors to increase data locality. With the data structure we describe, we achieve comparable performance on both the matrix-vector product and the solution of the sparse triangular systems on a variety of real problems, such as those arising from large scale reservoir simulation or structural analysis.     

Use of EM algorithm for data reduction under sparsity assumption

Recent scientific applications produce data that are too large for storing or rendering for further statistical analysis. This motivates the construction of an optimum mechanism to choose only a subset of the available information and drawing inferences about the parent population using only the stored subset. This paper addresses the issue of estimation of parameter from such filtered data. Instead of all the observations we observe only a few chosen linear combinations of them and treat the remaining information as missing. From the observed linear combinations we try to estimate the parameter using EM based technique under the assumption that the parameter is sparse. In this paper we propose two related methods called ASREM and ESREM. The methods developed here are also used for hypothesis testing and construction of confidence interval. Similar data filtering approach already exists in signal sampling paradigm, for example, Compressive Sampling introduced by Candes et al. (Commun Pure Appl Math 59(8):1207–1223, 2006) and Donoho (IEEE Trans Inf Theory 52: 1289–1306, 2006). The methods proposed in this paper are not claimed to outperform all the available techniques of signal recovery, rather our methods are suggested as an alternative way of data compression using EM algorithm. However, we shall compare our methods to one standard algorithm, viz., robust signal recovery from noisy data using min-\(\ell _{1}\) with quadratic constraints. Finally we shall apply one of our methods to a real life dataset.     

中等稀疏条件下基因交互作用的两步Bayes方法

植物遗传与基因组学研究表明许多重要的农艺性状有影响的基因位点不是稀疏的,受到大量微效基因的影响,并且还存在基因交互项的影响.本文基于重要油料作物油菜的花期数据,研究中等稀疏条件下的基因选择问题,提出了一种两步Bayes模型选择方法.考虑基因间的交互作用,模型的维数急剧增长,加上数据结构特别,通常的变量选择方法效果不好....     

Adaptive Image Processing: First Order PDE Constraint Regularizers and a Bilevel Training Scheme

Journal of Nonlinear Science - We discuss a system of two coupled parabolic equations that have degenerate diffusion constants depending on the energy-like variable. The dissipation of the...     

Convex optimization under combinatorial sparsity constraints

We present a heuristic approach for convex optimization problems containing different types of sparsity constraints. Whenever the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in every iteration. The entering non-zero is determined by considering the dual multipliers of the bounds on variables being fixed to zero. While this algorithm is purely heuristic, we show experimentally that it often finds near-optimal solutions for cardinality-constrained knapsack problems and for sparse regression problems.     

Adaptive wavelet methods and sparsity reconstruction for inverse heat conduction problems

This paper is concerned with the numerical treatment of inverse heat conduction problems. In particular, we combine recent results on the regularization of ill-posed problems by iterated soft shrinkage with adaptive wavelet algorithms for the forward problem. The analysis is applied to an inverse parabolic problem that stems from the industrial process of melting iron ore in a steel furnace. Some numerical experiments that confirm the applicability of our approach are presented.     

Numerical methods for A-optimal designs with a sparsity constraint for ill-posed inverse problems

We consider the problem of experimental design for linear ill-posed inverse problems. The minimization of the objective function in the classic A-optimal design is generalized to a Bayes risk minimization with a sparsity constraint. We present efficient algorithms for applications of such designs to large-scale problems. This is done by employing Krylov subspace methods for the solution of a subproblem required to obtain the experiment weights. The performance of the designs and algorithms is illustrated with a one-dimensional magnetotelluric example and an application to two-dimensional super-resolution reconstruction with MRI data.