Let A be a d by n matrix, d < n. Let C be the regular cross polytope (octahedron) in Rn. It has recently been shown that properties of the centrosymmetric polytope P = AC are of interest for finding sparse solutions to the underdetermined system of equations y = Ax; [9]. In particular, it is valuable to know that P is centrally k-neighborly. We study the face numbers of randomly-projected cross-polytopes in the proportional dimensional case where dn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rn. We derive ?N(d) > 0 with the property that, for any ? < ?N(d), with overwhelming probability for large d, the number of k-dimensional faces of P = AC is the same as for C, for 0 k d. This implies that P is centrally bdc-neighborly, and its skeleton Skel[? d](P) is combinatorially equivalent to Skel[? d]©. We display graphs of ?N. Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: facial neighborliness and sectional neighborliness [9]; we study both. The weakest, (k, e)-facial neighborliness, asks if the k-faces are all simplicial and if the numbers of k-dimensional faces fk(P) >= fk(C)(1 - e). We characterize and compute the critical proportion ?F (d) > 0 at which phase transition occurs in k/d. The other, (k, e)- sectional neighborliness, asks whether all, except for a small fraction epsilon, of the k-dimensional intrinsic sections of P are k-dimensional cross-polytopes. (Intrinsic sections intersect P with k-dimensional subspaces spanned by vertices of P.) We characterize and compute a proportion ?S(d) > 0 guaranteeing this property for k/d ~ ? < ?S(d). We display graphs of ?S and ?F.

Let A be a d by n matrix, d < n. Let T = T^n-1 be the standard regular simplex in R^n. We count the faces of the projected simplex AT in the case where the projection is random, the dimension d is large and n and d are comparable: d ~ dn, d in (0, 1). The projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of R^n. We derive ?N( d) > 0 with the property that, for any ? < ? N( deter), with overwhelming probability for large d, the number of k-dimensional faces of P = AT is exactly the same as for T, for 0<=k<= ?d. This implies that P is [?d]-neighborly, and its skeleton Skel[? d] ( P) is combinatorially equivalent to Skel[?d] (T). We display graphs of ?N. We also study a weaker notion of neighborliness it asks if the k-faces are all simplicial and if the numbers of k-dimensional faces fk(P) >= fk(T)(1-e). This was already considered by Vershik and Sporyshev, who obtained qualitative results about the existence of a threshold ? VS(d) > 0 at which phase transition occurs in k/d. We compute and display ?VS and compare to ?N. Our results imply that the convex hull of n Gaussian samples in R^d, with n large and proportional to d, ‘looks like a simplex’ in the following sense. In a typical realization of such a high-dimensional Gaussian point cloud d~ dn, all points are on the boundary of the convex hull, and all pairwise line segments, triangles, quadrangles, …, [?d]-angles are on the boundary, for ?<? N(d/n). Our results also quantify a precise phase transition in the ability of linear programming to find the sparsest nonnegative solution to typical systems of underdetermined linear equations; when there is a solution with fewer than ?VS(d/n)d nonzeros, linear programming will find that solution.

Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.

Consider an underdetermined system of linear equations y = Ax with known d*n matrix A and known y. We seek the sparsest nonnegative solution, i.e. the nonnegative x with fewest nonzeros satisfying y = Ax. In general this problem is NP-hard. However, for many matrices A there is a threshold phenomenon: if the sparsest solution is sufficiently sparse, it can be found by linear programming. In classical convex polytope theory, a polytope P is called k-neighborly if every set of k vertices of P span a face of P. Let aj denote the j-th column of A, 1<=_j<=_n, let a0 = 0 and let P denote the convex hull of the aj . We say P is outwardly k-neighborly if every subset of k vertices not including 0 spans a face of P. We show that outward k-neighborliness is completely equivalent to the statement that, whenever y = Ax has a nonnegative solution with at most k nonzeros, it is the nonnegative solution to y = Ax having minimal sum. Using this and classical results on polytope neighborliness we obtain two types of corollaries. First, because many [d/2]-neighborly polytopes are known, there are many systems where the sparsest solution is available by convex optimization rather than combinatorial optimization - provided the answer has fewer nonzeros than half the number of equations. We mention examples involving incompletely-observed Fourier transforms and Laplace transforms. Second, results on classical neighborliness of high-dimensional randomly-projected simplices imply that, if A is a typical uniformly-distributed random orthoprojector with n = 2d and n large, the sparsest nonnegative solution to y = Ax can be found by linear programming provided it has fewer nonzeros than 1/8 the number of equations. We also consider a notion of weak neighborliness, in which the overwhelming majority of k-sets of aj's not containing 0 span a face. This implies that most nonnegative vectors x with k nonzeros are uniquely determined by y = Ax. As a corollary of recent work counting faces of random simplices, it is known that most polytopes P generated by large n by 2n uniformly-distributed orthoprojectors A are weakly k-neighborly with k _~.558n. We infer that for most n by 2n underdetermined systems having a sparse solution with fewer nonzeros than roughly half the number of equations, the sparsest solution can be found by linear programming.

In compressed sensing, one takes n < N samples of an N -dimensional vector x0 using an n × N matrix A, obtaining un-dersampled measurements y = Ax0 . For random matrices with Gaussian i.i.d entries, it is known that, when x0 is k-sparse, there is a precisely determined phase transition: for a certain region in the (k/n, n/N )-phase diagram, convex optimization min ||x||_1 subject to y = Ax, x ∈ X^N typically finds the sparsest solution, while outside that region, it typically fails. It has been shown empirically that the same property – with the same phase transition location – holds for a wide range of non-Gaussian random matrix ensembles. We consider specific deterministic matrices including Spikes and Sines, Spikes and Noiselets, Paley Frames, Delsarte-Goethals Frames, Chirp Sensing Matrices, and Grassmannian Frames. Extensive experiments show that for a typical k-sparse object, convex optimization is successful over a region of the phase diagram that coincides with the region known for Gaussian matrices. In our experiments, we considered coefficients constrained to X^N for four different sets X ∈ {[0, 1], R_+ , R, C}. We establish this finding for each of the associated four phase transitions.

Shrinkage is a well known and appealing denoising technique, introduced originally by Donoho and Johnstone in 1994. The use of shrinkage for denoising is known to be optimal for Gaussian white noise, provided that the sparsity on the signal’s representation is enforced using a unitary transform. Still, shrinkage is also practiced with non-unitary, and even redundant representations, typically leading to very satisfactory results. In this paper we shed some light on this behavior. The main argument in this paper is that such simple shrinkage could be interpreted as the first iteration of an algorithm that solves the basis pursuit denoising (BPDN) problem. While the desired solution of BPDN is hard to obtain in general, we develop in this paper a simple iterative procedure for the BPDN minimization that amounts to step-wise shrinkage. We demonstrate how the simple shrinkage emerges as the first iteration of this novel algorithm. Furthermore, we show how shrinkage can be iterated, turning into an effective algorithm that minimizes the BPDN via simple shrinkage steps, in order to further strengthen the denoising effect.

Overcomplete representations are attracting interest in signal processing theory, particularly due to their potential to generate sparse representations of signals. However, in general, the problem of finding sparse representations must be unstable in the presence of noise. This paper establishes the possibility of stable recovery under a combination of sufficient sparsity and favorable structure of the overcomplete system. Considering an ideal underlying signal that has a sufficiently sparse representation, it is assumed that only a noisy version of it can be observed. Assuming further that the overcomplete system is incoherent, it is shown that the optimally sparse approximation to the noisy data differs from the optimally sparse decomposition of the ideal noiseless signal by at most a constant multiple of the noise level. As this optimal-sparsity method requires heavy (combinatorial) computational effort, approximation algorithms are considered. It is shown that similar stability is also available using the basis and the matching pursuit algorithms. Furthermore, it is shown that these methods result in sparse approximation of the noisy data that contains only terms also appearing in the unique sparsest representation of the ideal noiseless sparse signal.