Search

Low-rank matrix recovery has found many applications in science and engineering such as machine learning, system identification, and Euclidean embedding. However, the low-rank matrix recovery problem is an NP hard problem and thus challenging. A commonly used heuristic approach is the nuclear norm minimization. Recently, some authors established the necessary and sufficient null space conditions for nuclear norm minimization to recover every possible low-rank matrix with rank at most $r$ (the strong null space condition). Oymak et al. established a null space condition for successful recovery of a given low-rank matrix (the weak null space condition) using nuclear norm minimization, and derived the phase transition for the nuclear norm minimization. In this paper, we show that the weak null space condition proposed by Oymak et al. is only a sufficient condition for successful matrix recovery using nuclear norm minimization, and is not a necessary condition as claimed. We further give a weak null space condition for low-rank matrix recovery, which is both necessary and sufficient for the success of nuclear norm minimization. At the core of our derivation are an inequality for characterizing the nuclear norms of block matrices, and the conditions for equality to hold in that inequality. [ABSTRACT FROM AUTHOR]

It is well known that \ell 1 minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. Exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from independent identically distributed (i.i.d.) Gaussian measurements, have been computed and are referred to as weak thresholds. In this paper, we introduce a reweighted \ell 1 recovery algorithm composed of two steps: 1) a standard \ell 1 minimization step to identify a set of entries where the signal is likely to reside and 2) a weighted \ell 1 minimization step where entries outside this set are penalized. For signals where the non-sparse component entries are independent and identically drawn from certain classes of distributions, (including most well-known continuous distributions), we prove a strict improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive—over 20% in the example we consider. [ABSTRACT FROM AUTHOR]

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph G with n nodes, we derive bounds of the minimum number of measurements needed to recover any k -sparse vector over G ). Using the Erdős-Rényi random graph as an example, we characterize the dependence of M^{G}_{k,n} on the graph structure. This paper suggests that M^{G}_{k,n}$ may serve as a graph connectivity metric. [ABSTRACT FROM AUTHOR]

It is known that a high-dimensional sparse vector \bf x^* in \cal R^n can be recovered from low-dimensional measurements \bf y=A\bf x^* where A^m \times n(m < n) is the measurement matrix. In this paper, with A being a random Gaussian matrix, we investigate the recovering ability of \ell_p-minimization (0\leq p \leq 1) as p varies, where \ell_p-minimization returns a vector with the least \ell_p quasi-norm among all the vectors \bf x satisfying A\bf x=\bf y. Besides analyzing the performance of strong recovery where \ell_p-minimization is required to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of “weak” recovery of \ell_p-minimization (0\leq p < 1) where the aim is to recover all the sparse vectors on one support with a fixed sign pattern. When \alpha (:=m \over n) \rightarrow 1, we provide sharp thresholds of the sparsity ratio (i.e., percentage of nonzero entries of a vector) that differentiates the success and failure via \ell_p-minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0,1), while the threshold is 1 for \ell_1-minimization. We also explicitly demonstrate that \ell_p-minimization (p < 1) can return a denser solution than \ell_1-minimization. For any \alpha \in (0,1), we provide bounds of the sparsity ratio for strong recovery and weak recovery, respectively, below which \ell_p-minimization succeeds. Our bound of strong recovery improves on the existing bounds when \alpha is large. In particular, regarding the recovery threshold, this paper argues that \ell_p-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and \ell_1-minimization can outperform \ell_p-minimization for weak recovery. These are in contrast to traditional wisdom that \ell_p-minimization, though computationally more expensive, always has better sparse recovery ability than \ell_1-minimization since it is closer to \ell_0-minimization. Finally, we provide an intuitive explanation to our findings. Numerical examples are also used to unambiguously confirm and illustrate the theoretical predictions. [ABSTRACT FROM AUTHOR]

\ell_1 minimization is often used for recovering sparse signals from an under-determined linear system. In this paper, we focus on finding sharp performance bounds on recovering approximately sparse signals using \ell_1 minimization under noisy measurements. While the restricted isometry property is powerful for the analysis of recovering approximately sparse signals with noisy measurements, the known bounds on the achievable sparsityref refid="fnote1"/ asterisk="no" id="fnote1" paraThe “sparsity” in this paper means the size of the set of nonzero or significant elements in a signal vector.para level can be quite loose. The neighborly polytope analysis which yields sharp bounds for perfectly sparse signals cannot be readily generalized to approximately sparse signals. We start from analyzing a necessary and sufficient condition, the “balancedness” property of linear subspaces, for achieving a certain signal recovery accuracy. Then we give a unified null space Grassmann angle-based geometric framework to give sharp bounds on this “balancedness” property of linear subspaces. By investigating the “balancedness” property, this unified framework characterizes sharp quantitative tradeoffs between signal sparsity and the recovery accuracy of \ell1 minimization for approximately sparse signal. As a consequence, this generalizes the neighborly polytope result for perfectly sparse signals. Besides the robustness in the “strong” sense for all sparse signals, we also discuss the notions of “weak” and “sectional” robustness. Our results concern fundamental properties of linear subspaces and so may be of independent mathematical interest. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a nonuniform sparsity model and analyze the performance of an optimized weighted \ell_1 minimization over that sparsity model. In particular, we focus on a model where the entries of the unknown vector fall into two sets, with entries of each set having a specific probability of being nonzero. We propose a weighted \ell_1 minimization recovery algorithm and analyze its performance using a Grassmann angle approach. We compute explicitly the relationship between the system parameters—the weights, the number of measurements, the size of the two sets, the probabilities of being nonzero—so that when i.i.d. random Gaussian measurement matrices are used, the weighted \ell_1 minimization recovers a randomly selected signal drawn from the considered sparsity model with overwhelming probability as the problem dimension increases. This allows us to compute the optimal weights. We demonstrate through rigorous analysis and simulations that for the case when the support of the signal can be divided into two different subclasses with unequal sparsity fractions, the weighted \ell_1 minimization outperforms the regular \ell_1 minimization substantially. We also generalize our results to signal vectors with an arbitrary number of subclasses for sparsity. [ABSTRACT FROM AUTHOR]

This paper investigates the uniqueness of a nonnegative vector solution and the uniqueness of a positive semidefinite matrix solution to underdetermined linear systems. A vector solution is the unique solution to an underdetermined linear system only if the measurement matrix has a row-span intersecting the positive orthant. Focusing on two types of binary measurement matrices, Bernoulli 0–1 matrices and adjacency matrices of general expander graphs, we show that, in both cases, the support size of a unique nonnegative solution can grow linearly, namely O(n), with the problem dimension n. We also provide closed-form characterizations of the ratio of this support size to the signal dimension. For the matrix case, we show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique positive semidefinite matrix solution to the compressed linear observations. We further show that a randomly generated Gaussian linear compressed observations operator will satisfy this condition with overwhelmingly high probability. [ABSTRACT FROM AUTHOR]

We investigate the problem of reconstructing a high-dimensional nonnegative sparse vector from lower-dimensional linear measurements. While much work has focused on dense measurement matrices, sparse measurement schemes can be more efficient both with respect to signal sensing as well as reconstruction complexity. Known constructions use the adjacency matrices of expander graphs, which often lead to recovery algorithms which are much more efficient than \ell 1 minimization. However, prior constructions of sparse measurement matrices rely on expander graphs with very high expansion coefficients which make the construction of such graphs difficult and the size of the recoverable sets very small. In this paper, we introduce sparse measurement matrices for the recovery of nonnegative vectors, using perturbations of the adjacency matrices of expander graphs requiring much smaller expansion coefficients, hereby referred to as minimal expanders. We show that when \ell 1 minimization is used as the reconstruction method, these constructions allow the recovery of signals that are almost three orders of magnitude larger compared to the existing theoretical results for sparse measurement matrices. We provide for the first time tight upper bounds for the so called weak and strong recovery thresholds when \ell 1 minimization is used. We further show that the success of \ell 1 optimization is equivalent to the existence of a “unique” vector in the set of solutions to the linear equations, which enables alternative algorithms for \ell 1 minimization. We further show that the defined minimal expansion property is necessary for all measurement matrices for compressive sensing, (even when the non-negativity assumption is removed) therefore implying that our construction is tight. We finally present a novel recovery algorithm that exploits expansion and is much more computationally efficient compared to \ell 1 minimization. [ABSTRACT FROM PUBLISHER]