Influences of preconditioning on the mutual coherence and the restricted isometry property of Gaussian/Bernoulli measurement matrices

This article discusses the influence of preconditioning on the mutual coherence and the restricted isometry property of Gaussian or Bernoulli measurement matrices. The mutual coherence can be reduced by preconditioning, although it is fairly small due to the probability estimate of the event that it is less than any given number in (0, 1). This can be extended to a set that contains either of the two types of matrices with a high probability but a subset with Lebesgue measure zero. The numerical results illustrate the reduction in the mutual coherence of Gaussian or Bernoulli measurement matrices. However, the first property can be true after preconditioning for a large type of measurement matrices having the property of s-order restricted isometry and being full row rank. This leads to a better estimate of the condition number of the corresponding submatrices and a more accurate error estimate of the conjugate gradient methods for the least squares problems typically used in greedy-like recovery algorithms.     

AN EXTENDED BLOCK RESTRICTED ISOMETRY PROPERTY FOR SPARSE RECOVERY WITH NON-GAUSSIAN NOISE

We study the recovery conditions of weighted mixed $\ell_2/\ell_p$ minimization for block sparse signal reconstruction from compressed measurements when partial block support information is available. We show theoretically that the extended block restricted isometry property can ensure robust recovery when the data fidelity constraint is expressed in terms of an $\ell_q$ norm of the residual error, thus establishing a setting wherein we are not restricted to Gaussian measurement noise. We illustrate the results with a series of numerical experiments.     

The Road to Deterministic Matrices with the Restricted Isometry Property

The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.     

Dimensionality Reduction with Subgaussian Matrices: A Unified Theory

We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson–Lindenstrauss-type results obtained earlier for specific datasets. In particular, we recover and, in several cases, improve results for sets of sparse and structured sparse vectors, low-rank matrices and tensors, and smooth manifolds. In addition, we establish a new Johnson–Lindenstrauss embedding for datasets taking the form of an infinite union of subspaces of a Hilbert space.     

基于部分三角函数变换矩阵的块压缩感知测量方法

为了提高块压缩感知的测量效率和重构性能,根据离散余弦变换和离散正弦变换具有汇聚信号能量的特性,提出了基于重复块对角结构的部分离散余弦变换partial discrete cosine transform in repeated block diagonal structure,简称PDCT-RBDS和部分离散正弦变换partial discrete sine transform in repeated block diagonal structure简称PDST-RBDS的两种压缩感知测量方法.所采用的测量矩阵是一种低复杂度的结构化确定性矩阵, 满足受限等距性质.并得到一个与采样能量有关的受限等距常数和精确重构的测量数下限.通过与采用重复块对角结构的部分随机高斯矩阵和部分贝努利矩阵的图像压缩感知对比,结果表明PDCT-RBDS和PDST-RBDS重构的PSNR大约提高1---5dBSSIM提高约0.05, 所需的重构时间和测量矩阵的存储空间大大减少.该方法特别适合大规模图像压缩及实时视频数据处理场合.     

Convergence of projected Landweber iteration for matrix rank minimization

In this paper, we study the performance of the projected Landweber iteration (PLW) for the general low rank matrix recovery. The PLW was first proposed by Zhang and Chen (2010) [43] based on the sparse recovery algorithm APG (Daubechies et al., 2008) [14] in the matrix completion setting, and numerical experiments have been given to show its efficiency (Zhang and Chen, 2010) [43]. In this paper, we focus on providing a convergence rate analysis of the PLW in the general setting of low rank matrix recovery with the affine transform having the matrix restricted isometry property. We show robustness of the algorithm to noise with a strong geometric convergence rate even for noisy measurements provided that the affine transform satisfies a matrix restricted isometry property condition.     

Sparse recovery in probability via <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">q</Emphasis></Subscript>-minimization with Weibull random matrices for 0 &lt; <Emphasis Type="Italic">q</Emphasis> ≤ 1

Although Gaussian random matrices play an important role of measurement matrices in compressed sensing, one hopes that there exist other random matrices which can also be used to serve as the measurement matrices. Hence, Weibull random matrices induce extensive interest. In this paper, we first propose the l_2,q robust null space property that can weaken the D-RIP, and show that Weibull random matrices satisfy the l_2,q robust null space property with high probability. Besides, we prove that Weibull random matrices also possess the l _q quotient property with high probability. Finally, with the combination of the above mentioned properties, we give two important approximation characteristics of the solutions to the l _q -minimization with Weibull random matrices, one is on the stability estimate when the measurement noise e ∈ ? ⁿ needs a priori ||e||₂ ≤ ?, the other is on the robustness estimate without needing to estimate the bound of ||e||₂. The results indicate that the performance of Weibull random matrices is similar to that of Gaussian random matrices in sparse recovery.     

Sparse solutions to underdetermined Kronecker product systems

Three properties of matrices: the spark, the mutual incoherence and the restricted isometry property have recently been introduced in the context of compressed sensing. We study these properties for matrices that are Kronecker products and show how these properties relate to those of the factors. For the mutual incoherence we also discuss results for sums of Kronecker products.     

基于混合l_2/l_1范数极小化方法的块稀疏信号重构条件

研究压缩感知中的块稀疏信号重构问题,主要对混合l_2/l_1极小化方法建立了一类改进的可重构条件.具体地说,本文证明若测量矩阵满足条件δ_k+θ_(k,k)1,则混合l_2/l_1极小化方法可精确重构(无噪声情形)或鲁棒重构(有噪声情形)原始块k-稀疏信号.进而表明本文给出的新条件弱于现有文献所给出的条件.     

Deterministic bounds for restricted isometry in compressed sensing matrices

A new quality measure for compressed sensing matrices is considered and its non-trivial lower bound is obtained which depends on the matrix sizes only. A relation of the new estimate to the standard restricted isometry property is established. The tightness of the new result is discussed as well as some its consequences related to the known results in compressed sensing theory.     

Suprema of Chaos Processes and the Restricted Isometry Property

We present a new bound for suprema of a special type of chaos process indexed by a set of matrices, which is based on a chaining method. As applications we show significantly improved estimates for the restricted isometry constants of partial random circulant matrices and time‐frequency structured random matrices. In both cases the required condition on the number m of rows in terms of the sparsity s and the vector length n is m ? s log² s log² n. © 2014 Wiley Periodicals, Inc.     

Minimization of transformed $$L_1$$ penalty: theory,difference of convex function algorithm,and robust application in compressed sensing

We study the minimization problem of a non-convex sparsity promoting penalty function, the transformed \(l_1\) (TL1), and its application in compressed sensing (CS). The TL1 penalty interpolates \(l_0\) and \(l_1\) norms through a nonnegative parameter \(a \in (0,+\infty )\), similar to \(l_p\) with \(p \in (0,1]\), and is known to satisfy unbiasedness, sparsity and Lipschitz continuity properties. We first consider the constrained minimization problem, and discuss the exact recovery of \(l_0\) norm minimal solution based on the null space property (NSP). We then prove the stable recovery of \(l_0\) norm minimal solution if the sensing matrix A satisfies a restricted isometry property (RIP). We formulated a normalized problem to overcome the lack of scaling property of the TL1 penalty function. For a general sensing matrix A, we show that the support set of a local minimizer corresponds to linearly independent columns of A. Next, we present difference of convex algorithms for TL1 (DCATL1) in computing TL1-regularized constrained and unconstrained problems in CS. The DCATL1 algorithm involves outer and inner loops of iterations, one time matrix inversion, repeated shrinkage operations and matrix-vector multiplications. The inner loop concerns an \(l_1\) minimization problem on which we employ the Alternating Direction Method of Multipliers. For the unconstrained problem, we prove convergence of DCATL1 to a stationary point satisfying the first order optimality condition. In numerical experiments, we identify the optimal value \(a=1\), and compare DCATL1 with other CS algorithms on two classes of sensing matrices: Gaussian random matrices and over-sampled discrete cosine transform matrices (DCT). Among existing algorithms, the iterated reweighted least squares method based on \(l_{1/2}\) norm is the best in sparse recovery for Gaussian matrices, and the DCA algorithm based on \(l_1\) minus \(l_2\) penalty is the best for over-sampled DCT matrices. We find that for both classes of sensing matrices, the performance of DCATL1 algorithm (initiated with \(l_1\) minimization) always ranks near the top (if not the top), and is the most robust choice insensitive to the conditioning of the sensing matrix A. DCATL1 is also competitive in comparison with DCA on other non-convex penalty functions commonly used in statistics with two hyperparameters.     

A Few Remarks on the Operator Norm of Random Toeplitz Matrices

We present some results concerning the almost sure behavior of the operator norm of random Toeplitz matrices, including the law of large numbers for the norm, normalized by its expectation (in the i.i.d. case). As tools we present some concentration inequalities for suprema of empirical processes, which are refinements of recent results by Einmahl and Li.     

Concentration and convergence rates for spectral measures of random matrices

The topic of this paper is the typical behavior of the spectral measures of large random matrices drawn from several ensembles of interest, including in particular matrices drawn from Haar measure on the classical Lie groups, random compressions of random Hermitian matrices, and the so-called random sum of two independent random matrices. In each case, we estimate the expected Wasserstein distance from the empirical spectral measure to a deterministic reference measure, and prove a concentration result for that distance. As a consequence we obtain almost sure convergence of the empirical spectral measures in all cases.     

Linearly connected sequences and spectrally optimal dual frames for erasures

In the case that a frame is prescribed for applications and erasures occur in the process of data transmissions, we examine optimal dual frames for the recovery from single erasures. In contrast to earlier papers, we consider the spectral radius of the error operator instead of its operator norm as a measure of optimality. This notion of optimality is natural when the Neumann series is used to recover the original data in an iterative manner. We obtain a complete characterization of spectrally one-erasure optimal dual frames in terms of the redundancy distribution of the prescribed frame. Our characterization relies on the connection between erasure optimal frames and the linear connectivity property of the frame. We prove that the linear connectivity property is equivalent to the intersection dependent property, and is also closely related to the well-known concept of a k-independent set. Additionally, we also establish several necessary and sufficient conditions for the existence of an alternate dual frame to make the iterative reconstruction work.     

Refined Analysis of Sparse MIMO Radar

We analyze a multiple-input multiple-output (MIMO) radar model and provide recovery results for a compressed sensing (CS) approach. In MIMO radar different pulses are emitted by several transmitters and the echoes are recorded at several receiver nodes. Under reasonable assumptions the transformation from emitted pulses to the received echoes can approximately be regarded as linear. For the considered model, and many radar tasks in general, sparsity of targets within the considered angle-range-Doppler domain is a natural assumption. Therefore, it is possible to apply methods from CS in order to reconstruct the parameters of the targets. Assuming Gaussian random pulses the resulting measurement matrix becomes a highly structured random matrix. Our first main result provides an estimate for the well-known restricted isometry property (RIP) ensuring stable and robust recovery. We require more measurements than standard results from CS, like for example those for Gaussian random measurements. Nevertheless, we show that due to the special structure of the considered measurement matrix our RIP result is in fact optimal (up to possibly logarithmic factors). Our further two main results on nonuniform recovery (i.e., for a fixed sparse target scene) reveal how the fine structure of the support set—not only the size—affects the (nonuniform) recovery performance. We show that for certain “balanced” support sets reconstruction with essentially the optimal number of measurements is possible. Indeed, we introduce a parameter measuring the well-behavedness of the support set and resemble standard results from CS for near-optimal parameter choices. We prove recovery results for both perfect recovery of the support set in case of exactly sparse vectors and an \(\ell _2\)-norm approximation result for reconstruction under sparsity defect. Our analysis complements earlier work by Strohmer & Friedlander and deepens the understanding of the considered MIMO radar model. Thereby—and apparently for the first time in CS theory—we prove theoretical results in which the difference between nonuniform and uniform recovery consists of more than just logarithmic factors.     

Limit distributions of random matrices

We study limit distributions of independent random matrices as well as limit joint distributions of their blocks under normalized partial traces composed with classical expectation. In particular, we are concerned with the ensemble of symmetric blocks of independent Hermitian random matrices which are asymptotically free, asymptotically free from diagonal deterministic matrices, and whose norms are uniformly bounded almost surely. This class contains symmetric blocks of unitarily invariant Hermitian random matrices whose asymptotic distributions are compactly supported probability measures on the real line. Our approach is based on the concept of matricial freeness which is a generalization of freeness in free probability. We show that the associated matricially free Gaussian operators provide a unified framework for studying the limit distributions of sums and products of independent rectangular random matrices, including non-Hermitian Gaussian matrices and matrices of Wishart type.     

Hereditary tree growth and Lévy forests

We introduce the notion of a hereditary property for rooted real trees and we also consider reduction of trees by a given hereditary property. Leaf-length erasure, also called trimming, is included as a special case of hereditary reduction. We only consider the metric structure of trees, and our framework is the space $\mathbb{T}$ of pointed isometry classes of locally compact rooted real trees equipped with the Gromov–Hausdorff distance. We discuss general tightness criteria in $\mathbb{T}$ and limit theorems for growing families of trees. We apply these results to Galton–Watson trees with exponentially distributed edge lengths. This class is preserved by hereditary reduction. Then we consider families of such Galton–Watson trees that are consistent under hereditary reduction and that we call growth processes. We prove that the associated families of offspring distributions are completely characterised by the branching mechanism of a continuous-state branching process. We also prove that such growth processes converge to Lévy forests. As a by-product of this convergence, we obtain a characterisation of the laws of Lévy forests in terms of leaf-length erasure and we obtain invariance principles for discrete Galton–Watson trees, including the super-critical cases.     

The weak and strong Gaussian probabilistic realization problem

A classification is given of all σ-algebras that make two given σ-algebras conditionally independent in the case that the σ-algebras are generated by finite dimensional Gaussian random variables. In addition a classification is given of all Gaussian measures that have the conditional independence property and such that restricted to a subspace, they coincide with a given measure.     

基于非凸优化模型的块稀疏信号恢复条件

压缩感知(compressed sensing,CS)是一种全新的信息采集与处理理论，它表明稀疏信号能够在远低于Shannon-Nyquist采样率的条件下被精确重构.现从压缩感知理论出发，对块稀疏信号重构算法进行研究，通过混合l₂/l_q(0相似文献