Search

The use of generalized Lasso is a common technique for recovery of structured high-dimensional signals. There are three common formulations of generalized Lasso ; each program has a governing parameter whose optimal value depends on properties of the data. At this optimal value, compressed sensing theory explains why Lasso programs recover structured high-dimensional signals with minimax order-optimal error. Unfortunately in practice, the optimal choice is generally unknown and must be estimated. Thus, we investigate stability of each of the three Lasso programs with respect to its governing parameter. Our goal is to aid the practitioner in answering the following question: given real data, which Lasso program should be used? We take a step towards answering this by analysing the case where the measurement matrix is identity (the so-called proximal denoising setup) and we use |$\ell _{1}$| regularization. For each Lasso program, we specify settings in which that program is provably unstable with respect to its governing parameter. We support our analysis with detailed numerical simulations. For example, there are settings where a 0.1% underestimate of a Lasso parameter can increase the error significantly and a 50% underestimate can cause the error to increase by a factor of |$10^{9}$|⁠. [ABSTRACT FROM AUTHOR]

We study the problem of estimating a low-rank tensor when we have noisy observations of a subset of its entries. A rank- |$r$|⁠ , order- |$d$|⁠ , |$N \times N \times \cdots \times N$| tensor, where |$r=O(1)$|⁠ , has |$O(dN)$| free variables. On the other hand, prior to our work, the best sample complexity that was achieved in the literature is |$O\left(N^{\frac{d}{2}}\right)$|⁠ , obtained by solving a tensor nuclear-norm minimization problem. In this paper, we consider the 'M-norm', an atomic norm whose atoms are rank-1 sign tensors. We also consider a generalization of the matrix max-norm to tensors, which results in a quasi-norm that we call 'max-qnorm'. We prove that solving an M-norm constrained least squares (LS) problem results in nearly optimal sample complexity for low-rank tensor completion (TC). A similar result holds for max-qnorm as well. Furthermore, we show that these bounds are nearly minimax rate-optimal. We also provide promising numerical results for max-qnorm constrained TC, showing improved recovery compared to matricization and alternating LS. [ABSTRACT FROM AUTHOR]

We generalize the 1-bit matrix completion problem to higher order tensors. Consider a rank- $r$ order- $d$ tensor $T$ in $\mathbb {R}^{N} \times \cdots \times \mathbb {R}^{N}$ with bounded entries. We show that when $r=O(1)$ , such a tensor can be estimated efficiently from only $m=O_r(Nd)$ binary measurements. This shows that the sample complexity of recovering a low-rank tensor from 1-bit measurements of a subset of its entries is roughly the same as recovering it from unquantized measurements—a result that had been known only in the matrix case, i.e., when $d=2$. By using a certain atomic M-norm as a convex proxy for rank, we allow for approximately low-rank tensors and give error bounds based on the M-norm of the tensor. We prove that the theoretical bounds are optimal both in the M-norm bound and the size $N$. Moreover, we show the advantage of directly using the low-rank tensor structure, rather than matricization, both theoretically and numerically. Specifically, we show how the 1-bit measurement model can be used for context-aware recommender systems. [ABSTRACT FROM AUTHOR]

We study the problem of signal estimation from non-linear observations when the signal belongs to a low-dimensional set buried in a high-dimensional space. A rough heuristic often used in practice postulates that the non-linear observations may be treated as noisy linear observations, and thus, the signal may be estimated using the generalized Lasso. This is appealing because of the abundance of efficient, specialized solvers for this program. Just as noise may be diminished by projecting onto the lower dimensional space, the error from modeling non-linear observations with linear observations will be greatly reduced when using the signal structure in the reconstruction. We allow general signal structure, only assuming that the signal belongs to some set K \subset \mathbb R ^n . We consider the single-index model of non-linearity. Our theory allows the non-linearity to be discontinuous, not one-to-one and even unknown. We assume a random Gaussian model for the measurement matrix, but allow the rows to have an unknown covariance matrix. As special cases of our results, we recover near-optimal theory for noisy linear observations, and also give the first theoretical accuracy guarantee for 1-b compressed sensing with unknown covariance matrix of the measurement vectors. [ABSTRACT FROM AUTHOR]

Many applications have benefited remarkably from low-dimensional models in the recent decade. The fact that many signals, though high dimensional, are intrinsically low dimensional has given the possibility to recover them stably from a relatively small number of their measurements. For example, in compressed sensing with the standard (synthesis) sparsity prior and in matrix completion, the number of measurements needed is proportional (up to a logarithmic factor) to the signal’s manifold dimension. Recently, a new natural low-dimensional signal model has been proposed: the cosparse analysis prior. In the noiseless case, it is possible to recover signals from this model, using a combinatorial search, from a number of measurements proportional to the signal’s manifold dimension. However, if we ask for stability to noise or an efficient (polynomial complexity) solver, all the existing results demand a number of measurements, which is far removed from the manifold dimension, sometimes far greater. Thus, it is natural to ask whether this gap is a deficiency of the theory and the solvers, or if there exists a real barrier in recovering the cosparse signals by relying only on their manifold dimension. Is there an algorithm which, in the presence of noise, can accurately recover a cosparse signal from a number of measurements proportional to the manifold dimension? In this paper, we prove that there is no such algorithm. Furthermore, we show through the numerical simulations that even in the noiseless case convex relaxations fail when the number of measurements is comparable with the manifold dimension. This gives a practical counterexample to the growing literature on the compressed acquisition of signals based on manifold dimension. [ABSTRACT FROM PUBLISHER]

In this paper, we develop a theory of matrix completion for the extreme case of noisy 1-bit observations. Instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question we ask is whether or not it is possible to obtain an accurate estimate of M from this data. In general, this would seem impossible, but we show that the maximum likelihood estimate under a suitable constraint returns an accurate estimate of M when ∥M∥∞ ≤ α and rank(M) ≤ r. If the log-likelihood is a concave function (e.g. the logistic or probit observation models), then we can obtain this maximum likelihood estimate by optimizing a convex program. In addition, we also show that if instead of recovering M we simply wish to obtain an estimate of the distribution generating the 1-bit measurements, then we can eliminate the requirement that M when ∥M∥∞ ≤ α. For both cases, we provide lower bounds showing that these estimates are near-optimal. We conclude with a suite of experiments that both verify the implications of our theorems as well as illustrate some of the practical applications of 1-bit matrix completion. In particular, we compare our programme to standard matrix completion methods on movie rating data in which users submit ratings from 1 to 5. In order to use our program, we quantize this data to a single bit, but we allow the standard matrix completion program to have access to the original ratings (from 1 to 5). Surprisingly, the approach based on binary data performs significantly better. [ABSTRACT FROM AUTHOR]

Given a subset K of the unit Euclidean sphere, we estimate the minimal number m= m( K) of hyperplanes that generate a uniform tessellation of K, in the sense that the fraction of the hyperplanes separating any pair x, y∈ K is nearly proportional to the Euclidean distance between x and y. Random hyperplanes prove to be almost ideal for this problem; they achieve the almost optimal bound m= O( w( K)) where w( K) is the Gaussian mean width of K. Using the map that sends x∈ K to the sign vector with respect to the hyperplanes, we conclude that every bounded subset K of $\mathbb{R}^{n}$ embeds into the Hamming cube {−1,1} with a small distortion in the Gromov-Haussdorff metric. Since for many sets K one has m= m( K)≪ n, this yields a new discrete mechanism of dimension reduction for sets in Euclidean spaces. [ABSTRACT FROM AUTHOR]

This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We demonstrate that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We show that an s-sparse signal in \BBR^n can be accurately estimated from m = O(s\log (n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(s \log (2n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in \BBR^n which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension. [ABSTRACT FROM AUTHOR]

This paper introduces a simple and very general theory of compressive sensing. In this theory, the sensing mechanism simply selects sensing vectors independently at random from a probability distribution F; it includes all standard models—e.g., Gaussian, frequency measurements—discussed in the literature, but also provides a framework for new measurement strategies as well. We prove that if the probability distribution F obeys a simple incoherence property and an isotropy property, one can faithfully recover approximately sparse signals from a minimal number of noisy measurements. The novelty is that our recovery results do not require the restricted isometry property (RIP) to hold near the sparsity level in question, nor a random model for the signal. As an example, the paper shows that a signal with s nonzero entries can be faithfully recovered from about s \log n Fourier coefficients that are contaminated with noise. [ABSTRACT FROM AUTHOR]

This paper presents several novel theoretical results regarding the recovery of a low-rank matrix from just a few measurements consisting of linear combinations of the matrix entries. We show that properly constrained nuclear-norm minimization stably recovers a low-rank matrix from a constant number of noisy measurements per degree of freedom; this seems to be the first result of this nature. Further, with high probability, the recovery error from noisy data is within a constant of three targets: 1) the minimax risk, 2) an “oracle” error that would be available if the column space of the matrix were known, and 3) a more adaptive “oracle” error which would be available with the knowledge of the column space corresponding to the part of the matrix that stands above the noise. Lastly, the error bounds regarding low-rank matrices are extended to provide an error bound when the matrix has full rank with decaying singular values. The analysis in this paper is based on the restricted isometry property (RIP). [ABSTRACT FROM AUTHOR]

The Binary 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)}^{'}}$. [ABSTRACT FROM AUTHOR]

Abstract: In one-bit compressed sensing, previous results state that sparse signals may be robustly recovered when the measurements are taken using Gaussian random vectors. In contrast to standard compressed sensing, these results are not extendable to natural non-Gaussian distributions without further assumptions, as can be demonstrated by simple counter-examples involving extremely sparse signals. We show that approximately sparse signals that are not extremely sparse can be accurately reconstructed from single-bit measurements sampled according to a sub-gaussian distribution, and the reconstruction comes as the solution to a convex program. [Copyright &y& Elsevier]

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 {\mathbb R}^{n} can be estimated (up to normalization) from \Omega (s \log ~(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 \lambda := 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 . 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^{-\Omega (\lambda )} . 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. [ABSTRACT FROM AUTHOR]