This paper studies the performance of OMP in comparison to Thresholding in the case in which only a perturbed version of the generating dictionary is known. Both theory and numerical simulations show that simple Thresholding is a viable alternative to OMP in applications where only a perturbed version of the generating dictionary is given, such as dictionary learning.

The original paper uses a wrong assumption. In general, for disjoint index sets$A_i, B$and$J = A_i \cup B$with corresponding projections onto the column spans of subdictionaries$P(\Phi _J), P(\Phi _B), P(\Phi _{A_i})$rather than equality we have,$P(\Phi _J)[{\mathbb {I}}- P(\Phi _{A_i})]\ne P(\Phi _B)[{\mathbb {I}}- P(\Phi _{A_i})]$. We provide the corrected proof of Theorem II.1 as well as Theorem III.1. with corrected constants and proof.

We present a theoretical analysis of the average performance of orthogonal matching pursuit (OMP) for sparse approximation. For signals that are generated from a dictionary with K atoms and coherence μ and coefficients corresponding to a geometric sequence with parameter α2log K ≲ 1 - α. This improves by an order of magnitude over worst case results and shows that OMP and its famous competitor Basis Pursuit outperform each other depending on the setting.

This paper presents a simple randomised algorithm for recovering high-dimensional sparse functions, i.e. functions ƒ : [0, 1]d→ ℝ which depend effectively only on k out of d variables, meaning ƒ(x1, …, xd) = g(xi1, …, xik), where the indices 1 ≤ i1< i2< … < ik≤ d are unknown. It is shown that (under certain conditions on g) this algorithm recovers the k unknown coordinates with probability at least 1–6 exp(−L) using only O(k(L+log k)(L+log d)) samples of ƒ.

We present a new and computationally efficient scheme for classifying signals into a fixed number of known classes. We model classes as subspaces in which the corresponding data is well represented by a dictionary of features. In order to ensure low misclassification, the subspaces should be incoherent so that features of a given class cannot represent efficiently signals from another. We propose a simple iterative strategy to learn dictionaries which are are the same time good for approximating within a class and also discriminant. Preliminary tests on a standard face images database show competitive results.

This paper treats the problem of learning a dictionary providing sparse representations for a given signal class, via ℓ1-minimization. The problem can also be seen as factorizing a d × N matrix Y = (y1. . . yN), yn∈ ℝdof training signals into a d × K dictionary matrix Φ and a K × N coefficient matrix X = (x1. . . xN), xn∈ ℝK, which is sparse. The exact question studied here is when a dictionary coefficient pair (Φ, X) can be recovered as local minimum of a (nonconvex) ℓ1-criterion with input Y = Φ X. First, for general dictionaries and coefficient matrices, algebraic conditions ensuring local identifiability are derived, which are then specialized to the case when the dictionary is a basis. Finally, assuming a random Bernoulli-Gaussian sparse model on the coefficient matrix, it is shown that sufficiently incoherent bases are locally identifiable with high probability. The perhaps surprising result is that the typically sufficient number of training samples N grows up to a logarithmic factor only linearly with the signal dimension, i.e., N ≈ CK log K, in contrast to previous approaches requiring combinatorially many samples.

This paper extends the concept of compressed sensing to signals that are not sparse in an orthonormal basis but rather in a redundant dictionary. It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants. Thus, signals that are sparse with respect to the dictionary can be recovered via basis pursuit (BP) from a small number of random measurements. Further, thresholding is investigated as recovery algorithm for compressed sensing, and conditions are provided that guarantee reconstruction with high probability. The different schemes are compared by numerical experiments.

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter results in much weaker conditions on the dictionary. Numerical simulations confirm our theoretical findings and show that p-thresholding is an interesting low complexity alternative to simultaneous greedy or convex relaxation algorithms for processing sparse multichannel signals with balanced coefficients.

In this letter, we show that with high probability, the thresholding algorithm can recover signals that are sparse in a redundant dictionary as long as the 2-Babel function is growing slowly. This implies that it can succeed for sparsity levels up to the order of the ambient dimension. The theoretical bounds are illustrated with numerical simulations. As an application of the theory, sensing dictionaries for optimal average performance are characterized, and their performance is tested numerically.

This paper addresses the problem of sensing or recovering a signal s, captured by distributed low-complexity sensors. Each sensor observes a noisy version of the signal of interest, and independently forms an approximant of its observation. This approximant is sent to a central decoder that tries to recover the input signal by combining the multiple sensor outputs. We propose to use redundant dictionaries, and thresholding in the sensor nodes, in order to form sparse approximants of the noisy observations, with low computational complexity. We first show that the noise can actually be beneficial in the recovery of the correct components of the signal s, since it can advantageously perturb the naive thresholding scheme. Then we illustrate the benefit of multiple observations with uncorrelated noise. By careful reconstruction with a projection onto convex sets (POCS) strategy, each additional measurement actually helps to recover more and more components of the original signal, since it tends to isolate the common part in all observations. Experimental results demonstrate the interesting recovery performance of our distributed sensing system. They show that a few observations, represented by a small number of components, are able to provide a good approximation of the signal, even in very noisy conditions