We consider the problem of recovering a function over the space of permutations (or, the symmetric group) over @math elements from given partial information; the partial information we consider is related to the group theoretic Fourier Transform of the function. This problem naturally arises in several settings such as ranked elections, multi-object tracking, ranking systems, and recommendation systems. Inspired by the work of Donoho and Stark in the context of discrete-time functions, we focus on non-negative functions with a sparse support (support size @math domain size). Our recovery method is based on finding the sparsest solution (through @math optimization) that is consistent with the available information. As the main result, we derive sufficient conditions for functions that can be recovered exactly from partial information through @math optimization. Under a natural random model for the generation of functions, we quantify the recoverability conditions by deriving bounds on the sparsity (support size) for which the function satisfies the sufficient conditions with a high probability as @math . @math optimization is computationally hard. Therefore, the popular compressive sensing literature considers solving the convex relaxation, @math optimization, to find the sparsest solution. However, we show that @math optimization fails to recover a function (even with constant sparsity) generated using the random model with a high probability as @math . In order to overcome this problem, we propose a novel iterative algorithm for the recovery of functions that satisfy the sufficient conditions. Finally, using an Information Theoretic framework, we study necessary conditions for exact recovery to be possible.
The sparsest recovery approach of this paper is similar (in flavor) to the above stated work; in fact, as is shown subsequently, the partial information we consider can be written as a linear transform of the function @math . However, the methods or approaches of the prior work do not apply. Specifically, the work considers finding the sparsest function consistent with the given partial information by solving the corresponding @math relaxation problem. The work derives a necessary and sufficient condition, called the Restricted Nullspace Property , on the structure of the matrix @math that guarantees that the solutions to the @math and @math relaxation problems are the same (see @cite_18 @cite_23 ). However, such sufficient conditions trivially fail in our setup (see @cite_8 ). Therefore, our work provides an alternate set of conditions that guarantee efficient recovery of the sparsest function.
@cite_18 @cite_23 @cite_8
2951576330 2003571173 2536849891 2168831133
We investigate the sparse recovery problem of reconstructing a high-dimensional non-negative sparse vector from lower dimensional linear measurements. While much work has focused on dense measurement matrices, sparse measurement schemes are crucial in applications, such as DNA microarrays and sensor networks, where dense measurements are not practically feasible. One possible construction uses the adjacency matrices of expander graphs, which often leads to recovery algorithms much more efficient than @math minimization. However, to date, constructions based on expanders have required very high expansion coefficients which can potentially make the construction of such graphs difficult and the size of the recoverable sets small. In this paper, we construct sparse measurement matrices for the recovery of non-negative vectors, using perturbations of the adjacency matrix of an expander graph with much smaller expansion coefficient. We present a necessary and sufficient condition for @math optimization to successfully recover the unknown vector and obtain expressions for the recovery threshold. For certain classes of measurement matrices, this necessary and sufficient condition is further equivalent to the existence of a "unique" vector in the constraint set, which opens the door to alternative algorithms to @math minimization. We further show that the minimal expansion we use is necessary for any graph for which sparse recovery is possible and that therefore our construction is tight. We finally present a novel recovery algorithm that exploits expansion and is much faster than @math optimization. Finally, we demonstrate through theoretical bounds, as well as simulation, that our method is robust to noise and approximate sparsity. This paper considers the problem of recovering an unknown sparse p×p matrix X from an m×m matrix Y=AXB T , where A and B are known m×p matrices with m≪p. The main result shows that there exist constructions of the sketching matrices A and B so that even if X has O(p) nonzeros, it can be recovered exactly and efficiently using a convex program as long as these nonzeros are not concentrated in any single row column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as m = O(√(# nonzeros in X) × log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require nonstandard techniques. Indeed, our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest. This problem is motivated by the following application, among others. Consider a p×n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DD T is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S=AD with A ∈ R m×p . We study the recovery of sparse vectors from subsampled random convolutions via @math -minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a subgaussian generator with independent entries, we improve previously known estimates: if the sparsity @math is small enough, i.e., @math , we show that @math measurements are sufficient to recover @math -sparse vectors in dimension @math with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If @math is larger, then essentially @math measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques which should be of independent interest. The goal of (stable) sparse recovery is to recover a @math -sparse approximation @math of a vector @math from linear measurements of @math . Specifically, the goal is to recover @math such that @math for some constant @math and norm parameters @math and @math . It is known that, for @math or @math , this task can be accomplished using @math non-adaptive measurements CRT06:Stable-Signal and that this bound is tight DIPW, FPRU, PW11 . In this paper we show that if one is allowed to perform measurements that are adaptive , then the number of measurements can be considerably reduced. Specifically, for @math and @math we show A scheme with @math measurements that uses @math rounds. This is a significant improvement over the best possible non-adaptive bound. A scheme with @math measurements that uses two rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type.