Binary measurements arise naturally in a variety of statistics and engineering applications. They may be inherent to the problem-for example, in determining the relationship between genetics and the presence or absence of a disease-or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, s-sparse signals in Rn can be estimated (up to normalization) from Ω(slog (n/s)) one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor λ := m/(s log(n/s)), where m is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by Ω(λ-1). Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible. However, we show that an adaptive choice of the thresholds used for quantization can lower the error rate to e-Ω(λ). This improves upon guarantees for other methods of adaptive thresholding, such as sigma- delta quantization. We develop a general recursive strategy to achieve this exponential decay and two specific polynomial-time algorithms, which fall into this framework, one based on convex programming and one on hard thresholding. Our work bridges the one-bit compressed sensing model, in which the engineer controls the measurement procedure, to sigma-delta and successive approximation quantization. Moreover, the principle is extendable to signal reconstruction problems in a variety of binary statistical models as well as statistical estimation problems like logistic regression.

Consider the problem of reconstructing a multidimensional signal from an underdetermined set of measurements, as in the setting of compressed sensing. Without any additional assumptions, this problem is ill-posed. However, for signals such as natural images or movies, the minimal total variation estimate consistent with the measurements often produces a good approximation to the underlying signal, even if the number of measurements is far smaller than the ambient dimensionality. This paper extends recent reconstruction guarantees for two-dimensional images x ∈ ℂ ^N2 to signals x ∈ ℂ ^Nd of arbitrary dimension d ≥ 2 and to isotropic total variation problems. In this paper, we show that a multidimensional signal x ∈ ℂ ^Nd can be reconstructed from O(s dlog(N ^d )) linear measurements y = Ax using total variation minimization to a factor of the best s-term approximation of its gradient. The reconstruction guarantees we provide are necessarily optimal up to polynomial factors in the spatial dimension d.

Motivated by recent work on stochastic gradient descent methods, we develop two stochastic variants of greedy algorithms for possibly non-convex optimization problems with sparsity constraints. We prove linear convergence¹ in expectation to the solution within a specified tolerance. This generalized framework is specialized to the problems of sparse signal recovery in compressed sensing and low-rank matrix recovery, giving methods with provable convergence guarantees that often outperform their deterministic counterparts. We also analyze the settings, where gradients and projections can only be computed approximately, and prove the methods are robust to these approximations. We include many numerical experiments, which align with the theoretical analysis and demonstrate these improvements in several different settings.

We generalize the concept of adaptive sampling rules to the sketch-and-project method for solving linear systems. Analyzing adaptive sampling rules in the sketch-and-project setting yields converge...