Compressed sensing (CS) is a paradigm in which a structured high-dimensional signal may be recovered from random, under-determined, and corrupted linear measurements. Lasso programs are effective for solving CS problems due to their proven ability to leverage underlying signal structure. Three popular Lasso programs are equivalent in a sense and sometimes used interchangeably. Tuned by a governing parameter, each admit an optimal parameter choice. For sparse or low-rank signal structures, this choice yields minimax order-optimal error. While CS is well-studied, existing theory for Lasso programs typically concerns this optimally tuned setting. However, the optimal parameter value for a Lasso program depends on properties of the data, and is typically unknown in practical settings. Performance in empirical problems thus hinges on a program’s parameter sensitivity: it is desirable that small variation about the optimal parameter choice begets small variation about the optimal risk. We examine the risk for these three programs and demonstrate that their parameter sensitivity can differ for the same data. We prove agauge-constrainedLasso program admits asymptotic cusp-like behaviour of its risk in the limiting low-noise regime. We prove that aresidual-constrainedLasso program has asymptotically suboptimal risk for very sparse vectors. These results contrast observations about anunconstrainedLasso program, which is relatively less sensitive to its parameter choice. We support the asymptotic theory with numerical simulations, demonstrating that parameter sensitivity of Lasso programs is readily observed for even modest dimensional parameters. Importantly, these simulations demonstrate regimes in which a Lasso program exhibits sensitivity to its parameter choice, though the other two do not. We hope this work aids practitioners in selecting a Lasso program for their problem.

TheBinary Iterative Hard Thresholding(BIHT) algorithm is a popular reconstruction method for one-bit compressed sensing due to its simplicity and fast empirical convergence. Despite considerable research on this algorithm, a theoretical understanding of the corresponding approximation error and convergence rate still remains an open problem. This paper shows that the normalized version of BIHT (NBIHT) achieves an approximation error rate optimal up to logarithmic factors. More precisely, using$m$one-bit measurements of an$s$-sparse vector$x$, we prove that the approximation error of NBIHT is of order$O \left ({\frac{1 }{ m }}\right)$up to logarithmic factors, which matches the information-theoretic lower bound$\Omega \left ({\frac{1 }{ m }}\right)$proved by Jacques, Laska, Boufounos, and Baraniuk in 2013. To our knowledge, this is the first theoretical analysis of a BIHT-type algorithm that explains the optimal rate of error decay empirically observed in the literature. This also makes NBIHT the first provable computationally-efficient one-bit compressed sensing algorithm that breaks the inverse square-root error decay rate$O \left ({\frac{1 }{ m^{1/2} }}\right)\vphantom {{\left ({\frac{1 }{ m^{1/2} }}\right)}^{'}}$.

We consider the problem of recovering an unknown latent code vector under a known generative model. For a $d$-layer deep generative network $\mathcal{G}:\mathbb{R}^{n_0}\rightarrow \mathbb{R}^{n_d}$ with ReLU activation functions, let the observation be $\mathcal{G}(x)+\epsilon$ where $\epsilon$ is noise. We introduce a simple novel algorithm, Partially Linearized Update for Generative Inversion (PLUGIn), to estimate $x$ (and thus $\mathcal{G}(x)$). We prove that, when weights are Gaussian and layer widths $n_i \gtrsim 5^i n_0$ (up to log factors), the algorithm converges geometrically to a neighbourhood of $x$ with high probability. Note the inequality on layer widths allows $n_i>n_{i+1}$ when $i\geq 1$. To our knowledge, this is the first such result for networks with some contractive layers. After a sufficient number of iterations, the estimation errors for both $x$ and $\mathcal{G}(x)$ are at most in the order of $\sqrt{4^dn_0/n_d} \|\epsilon\|$. Thus, the algorithm can denoise when the expansion ratio $n_d/n_0$ is large. Numerical experiments on synthetic data and real data are provided to validate our theoretical results and to illustrate that the algorithm can effectively remove artifacts in an image.

Compressed sensing is now established as an effective method for dimension reduction when the underlying signals are sparse or compressible with respect to some suitable basis or frame. One important, yet under-addressed problem regarding the compressive acquisition of analog signals is how to perform quantization. This is directly related to the important issues of how “compressed” compressed sensing is (in terms of the total number of bits one ends up using after acquiring the signal) and ultimately whether compressed sensing can be used to obtain compressed representations of suitable signals. In this paper, we propose a concrete and practicable method for performing “analog-to-information conversion”. Following a compressive signal acquisition stage, the proposed method consists of a quantization stage, based on ΣΔ (sigma-delta) quantization, and a subsequent encoding (compression) stage that fits within the framework of compressed sensing seamlessly. We prove that, using this method, we can convert analog compressive samples to compressed digital bitstreams and decode using tractable algorithms based on convex optimization. We prove that the proposed analog-to-information converter (AIC) provides a nearly optimal encoding of sparse and compressible signals. Finally, we present numerical experiments illustrating the effectiveness of the proposed AIC.

In this note we study the under-addressed quantization stage implicit in any compressed sensing signal acquisition paradigm. We also study the problem of compressing the bitstream resulting from the quantization. We propose using Sigma-Delta (ΣΔ) quantization followed by a compression stage comprised of a discrete Johnson-Lindenstrauss embedding, and a subsequent reconstruction scheme based on convex optimization. We show that this encoding/decoding method yields near-optimal rate-distortion guarantees for sparse and compressible signals and is robust to noise. Our results hold for sub-Gaussian (including Gaussian and Bernoulli) random compressed sensing measurements, and they hold for high bit-depth quantizers as well as for coarse quantizers including 1-bit quantization.

Recurrent neural networks are powerful tools for handling incomplete data problems in computer vision, thanks to their significant generative capabilities. However, the computational demand for these algorithms is too high to work in real time, without specialized hardware or software solutions. In this paper, we propose a framework for augmenting recurrent processing capabilities into a feedforward network without sacrificing much from computational efficiency. We assume a mixture model and generate samples of the last hidden layer according to the class decisions of the output layer, modify the hidden layer activity using the samples, and propagate to lower layers. For visual occlusion problem, the iterative procedure emulates feedforward-feedback loop, filling-in the missing hidden layer activity with meaningful representations. The proposed algorithm is tested on a widely used dataset and shown to achieve 2× improvement in classification accuracy for occluded objects. When compared to Restricted Boltzmann Machines, our algorithm shows superior performance for occluded object classification.

This letter introduces a novel framework of reservoir computing that is capable of both connectionist machine intelligence and symbolic computation. A cellular automaton is used as the reservoir of dynamical systems. Input is randomly projected onto the initial conditions of automaton cells, and nonlinear computation is performed on the input via application of a rule in the automaton for a period of time. The evolution of the automaton creates a space-time volume of the automaton state space, and it is used as the reservoir. The proposed framework is shown to be capable of long-term memory, and it requires orders of magnitude less computation compared to echo state networks. As the focus of the letter, we suggest that binary reservoir feature vectors can be combined using Boolean operations as in hyperdimensional computing, paving a direct way for concept building and symbolic processing. To demonstrate the capability of the proposed system, we make analogies directly on image data by asking, What is the automobile of air?

In this paper, we propose a support driven reweighted ℓ1minimization algorithm (SDRL1) that solves a sequence of weighted ℓ1problems and relies on the support estimate accuracy. Our SDRL1 algorithm is related to the IRL1 algorithm proposed by Candès, Wakin, and Boyd. We demonstrate that it is sufficient to find support estimates with good accuracy and apply constant weights instead of using the inverse coefficient magnitudes to achieve gains similar to those of IRL1. We then prove that given a support estimate with sufficient accuracy, if the signal decays according to a specific rate, the solution to the weighted ℓ1minimization problem results in a support estimate with higher accuracy than the initial estimate. We also show that under certain conditions, it is possible to achieve higher estimate accuracy when the intersection of support estimates is considered. We demonstrate the performance of SDRL1 through numerical simulations and compare it with that of IRL1 and standard ℓ1minimization.

In this paper, we propose an adaptive compressed sensing scheme that utilizes a support estimate to focus the measurements on the large valued coefficients of a compressible signal. We embed a “sparse-filtering” stage into the measurement matrix by weighting down the contribution of signal coefficients that are outside the support estimate. We present an application which can benefit from the proposed sampling scheme, namely, video compressive acquisition. We demonstrate that our proposed adaptive CS scheme results in a significant improvement in reconstruction quality compared with standard CS as well as adaptive recovery using weighted ℓ1minimization.

We study recovery conditions of weightedl1minimization for signal reconstruction from compressed sensing measurements when partial support information is available. We show that if at least 50% of the (partial) support information is accurate, then weightedl1minimization is stable and robust under weaker sufficient conditions than the analogous conditions for standardl1minimization. Moreover, weightedl1minimization provides better upper bounds on the reconstruction error in terms of the measurement noise and the compressibility of the signal to be recovered. We illustrate our results with extensive numerical experiments on synthetic data and real audio and video signals.

This paper proposes a novel Nyquist-rate analog-to-digital (A/D) conversion algorithm which achieves exponential accuracy in the bit-rate despite using imperfect components. The proposed algorithm is based on a robust implementation of a beta-encoder with β = φ = (1 + √5)/2, the golden ratio. It was previously shown that beta-encoders can be implemented in such a way that their exponential accuracy is robust against threshold offsets in the quantizer element. This paper extends this result by allowing for imperfect analog multipliers with imprecise gain values as well. Furthermore, a formal computational model for algorithmic encoders and a general test bed for evaluating their robustness is proposed.

Sparco is a framework for testing and benchmarking algorithms for sparse reconstruction. It includes a large collection of sparse reconstruction problems drawn from the imaging, compressed sensing, and geophysics literature. Sparco is also a framework for implementing new test problems and can be used as a tool for reproducible research. Sparco is implemented entirely in Matlab, and is released as open-source software under the GNU Public License.

We present theoretical results pertaining to the ability of lscrpminimization to recover sparse and compressible signals from incomplete and noisy measurements. In particular, we extend the results of Candes, Romberg and Tao (2005) to the ppminimization with certain values of p1minimization does. This is especially true when the restricted isometry constants are relatively large.

It was recently proved that a sound and complete qualitative simulator does not exist, that is, as long as the input-output vocabulary of the state-of-the-art QSIM algorithm is used, there will always be input models which cause any simulator with a coverage guarantee to make spurious predictions in its output. In this paper, we examine whether a meaningfully expressive restriction of this vocabulary is possible so that one can build a simulator with both the soundness and completeness properties. We prove several negative results: All sound qualitative simulators, employing subsets of the QSIM representation which retain the operating region transition feature, and support at least the addition and constancy constraints, are shown to be inherently incomplete. Even when the simulations are restricted to run in a single operating region, a constraint vocabulary containing just the addition, constancy, derivative, and multiplication relations makes the construction of sound and complete qualitative simulators impossible.

The K-level Sigma-Delta (/spl Sigma//spl Delta/) scheme with step size /spl delta/ is introduced as a technique for quantizing finite frame expansions for /spl Ropf//sup d/. Error estimates for various quantized frame expansions are derived, and, in particular, it is shown that /spl Sigma//spl Delta/ quantization of a unit-norm finite frame expansion in /spl Ropf//sup d/ achieves approximation error where N is the frame size, and the frame variation /spl sigma/(F,p) is a quantity which reflects the dependence of the /spl Sigma//spl Delta/ scheme on the frame. Here /spl par//spl middot//spl par/ is the d-dimensional Euclidean 2-norm. Lower bounds and refined upper bounds are derived for certain specific cases. As a direct consequence of these error bounds one is able to bound the mean squared error (MSE) by an order of 1/N/sup 2/. When dealing with sufficiently redundant frame expansions, this represents a significant improvement over classical pulse-code modulation (PCM) quantization, which only has MSE of order 1/N under certain nonrigorous statistical assumptions. /spl Sigma//spl Delta/ also achieves the optimal MSE order for PCM with consistent reconstruction.

Beta-encoders with error correction were introduced by Daubechies, DeVore, Guumlntuumlrk and Vaishampayan as an alternative to pulse-code modulation (PCM) for analog-to-digital conversion. An N-bit beta-encoder quantizes a real number by computing one of its N-bit truncated beta-expansions where betaisin(1,2) determines the base of expansion. These encoders have (almost) optimal rate-distortion properties like PCM; furthermore, they exploit the redundancy of beta-expansions and thus they are robust with respect to quantizer imperfections. However, these encoders have the shortcoming that the decoder needs to know the value of the base of expansion beta, a gain factor in the circuit used by the encoder, which is an impractical constraint. We present a method to implement beta-encoders so that they are also robust with respect to uncertainties of the value of beta. The method relies upon embedding the value of beta in the encoded bitstream. We show that this can be done without a priori knowledge of beta by the transmitting party. Moreover the algorithm still works if the value of beta changes (slowly) during the implementation

It is shown that sigma-delta (/spl Sigma//spl Delta/) algorithms can be used effectively to quantize finite frame expansions for R/sup d/. Error estimates for various quantized frame expansions are derived, and, in particular, it is shown that /spl Sigma//spl Delta/ quantizers outperform the standard PCM schemes.

It is possible to blindly separate an arbitrary number of sources given just two anechoic mixtures provided the time-frequency representations of the sources do not overlap, a condition which we call W-disjoint orthogonality. We define a power weighted two-dimensional histogram constructed from the ratio of the time-frequency representations of the mixtures which is shown to have one peak for each source with: peak location corresponding to the relative amplitude and delay mixing parameters. All of the time-frequency points which yield estimates in a given peak are exactly all the non-zero magnitude components of one of the sources. We introduce the concept of approximate W-disjoint orthogonality, present experimental results demonstrating the level of approximate W-disjoint orthogonality of speech in mixtures of various order, and show that even with imperfect W-disjoint orthogonality the histogram can be used to determine the mixing parameters and separate sources. Example demixing results can be found online: http://www.princeton.edu/∼srickard/bss.html

We present a novel method for blind separation of any number of sources using only two mixtures. The method applies when sources are (W-)disjoint orthogonal, that is, when the supports of the (windowed) Fourier transform of any two signals in the mixture are disjoint sets. We show that, for anechoic mixtures of attenuated and delayed sources, the method allows one to estimate the mixing parameters by clustering ratios of the time-frequency representations of the mixtures. The estimates of the mixing parameters are then used to partition the time-frequency representation of one mixture to recover the original sources. The technique is valid even in the case when the number of sources is larger than the number of mixtures. The general results are verified on both speech and wireless signals.