skip to main content

Title: Extreme Compressed Sensing of Poisson Rates from Multiple Measurements
Compressed sensing (CS) is a signal processing technique that enables the efficient recovery of a sparse high-dimensional signal from low-dimensional measurements. In the multiple measurement vector (MMV) framework, a set of signals with the same support must be recovered from their corresponding measurements. Here, we present the first exploration of the MMV problem where signals are independently drawn from a sparse, multivariate Poisson distribution. We are primarily motivated by a suite of biosensing applications of microfluidics where analytes (such as whole cells or biomarkers) are captured in small volume partitions according to a Poisson distribution. We recover the sparse parameter vector of Poisson rates through maximum likelihood estimation with our novel Sparse Poisson Recovery (SPoRe) algorithm. SPoRe uses batch stochastic gradient ascent enabled by Monte Carlo approximations of otherwise intractable gradients. By uniquely leveraging the Poisson structure, SPoRe substantially outperforms a comprehensive set of existing and custom baseline CS algorithms. Notably, SPoRe can exhibit high performance even with one-dimensional measurements and high noise levels. This resource efficiency is not only unprecedented in the field of CS but is also particularly potent for applications in microfluidics in which the number of resolvable measurements per partition is often severely limited. We prove more » the identifiability property of the Poisson model under such lax conditions, analytically develop insights into system performance, and confirm these insights in simulated experiments. Our findings encourage a new approach to biosensing and are generalizable to other applications featuring spatial and temporal Poisson signals. « less
; ; ;
Award ID(s):
1911094 2017712 1838177 1730574
Publication Date:
Journal Name:
Sponsoring Org:
National Science Foundation
More Like this
  1. Feature extraction, such as spectral occupancy, interferer energy and type, or direction-of-arrival, from wideband radio-frequency (RF) signals finds use in a growing number of applications as it enhances RF transceivers with cognitive abilities and enables parameter tuning of traditional RF chains. In power and cost limited applications, e.g., for sensor nodes in the Internet of Things, wideband RF feature extraction with conventional, Nyquist-rate analog-to-digital converters is infeasible. However, the structure of many RF features (such as signal sparsity) enables the use of compressive sensing (CS) techniques that acquire such signals at sub-Nyquist rates; while such CS-based analog-to-information (A2I) converters have the potential to enable low-cost and energy-efficient wideband RF sensing, they suffer from a variety of real-world limitations, such as noise folding, low sensitivity, aliasing, and limited flexibility. This paper proposes a novel CS-based A2I architecture called non-uniform wavelet sampling. Our solution extracts a carefully-selected subset of wavelet coefficients directly in the RF domain, which mitigates the main issues of existing A2I converter architectures. For multi-band RF signals, we propose a specialized variant called non-uniform wavelet bandpass sampling (NUWBS), which further improves sensitivity and reduces hardware complexity by leveraging the multi-band signal structure. We use simulations to demonstrate that NUWBSmore »approaches the theoretical performance limits of ℓ₁-norm-based sparse signal recovery. We investigate hardware-design aspects and show ASIC measurement results for the wavelet generation stage, which highlight the efficacy of NUWBS for a broad range of RF feature extraction tasks in cost- and power-limited applications.« less
  2. Sparse reconstruction algorithms aim to retrieve high-dimensional sparse signals from a limited number of measurements. A common example is LASSO or Basis Pursuit where sparsity is enforced using an `1-penalty together with a cost function ||y − Hx||_2^2. For random design matrices H, a sharp phase transition boundary separates the ‘good’ parameter region where error-free recovery of a sufficiently sparse signal is possible and a ‘bad’ regime where the recovery fails. However, theoretical analysis of phase transition boundary of the correlated variables case lags behind that of uncorrelated variables. Here we use replica trick from statistical physics to show that when an Ndimensional signal x is K-sparse and H is M × N dimensional with the covariance E[H_{ia}H_{jb}] = 1 M C_{ij}D_{ab}, with all D_{aa} = 1, the perfect recovery occurs at M ∼ ψ_K(D)K log(N/M) in the very sparse limit, where ψ_K(D) ≥ 1, indicating need for more observations for the same degree of sparsity.
  3. We develop a projected Nesterov’s proximal-gradient (PNPG) scheme for reconstructing sparse signals from compressive Poisson-distributed measurements with the mean signal intensity that follows an affine model with known intercept. The objective function to be minimized is a sum of convex data fidelity (negative log-likelihood (NLL)) and regularization terms. We apply sparse signal regularization where the signal belongs to a nonempty closed convex set within the domain of the NLL and signal sparsity is imposed using total-variation (TV) penalty. We present analytical upper bounds on the regularization tuning constant. The proposed PNPG method employs projected Nesterov’s acceleration step, function restart, and an adaptive step-size selection scheme that aims at obtaining a good local majorizing function of the NLL and reducing the time spent backtracking. We establish O(k⁻²) convergence of the PNPG method with step-size backtracking only and no restart. Numerical examples demonstrate the performance of the PNPG method.
  4. Feature extraction from wideband radio-frequency (RF) signals, such as spectral activity, interferer energy and type, or direction- of-arrival, finds use in a growing number of applications. Compressive sensing (CS)-based analog-to-information (A2I) converters enable the design of inexpensive and energy-efficient wideband RF sensing solutions for such applications. However, most A2I architectures suffer from a variety of real-world impairments. We propose a novel A2I architecture, referred to as non-uniform wavelet bandpass sampling (NUWBS). Our architecture extracts a carefully-tuned subset of wavelet coefficients directly in the RF domain, which mitigates the main issues of most existing A2I converters. We use simulations to show that NUWBS approaches the performance limits of l1-norm-based sparse signal recovery.
  5. We study high-dimensional signal recovery from non-linear measurements with design vectors having elliptically symmetric distribution. Special attention is devoted to the situation when the unknown signal belongs to a set of low statistical complexity, while both the measurements and the design vectors are heavy-tailed. We propose and analyze a new estimator that adapts to the structure of the problem, while being robust both to the possible model misspecification characterized by arbitrary non-linearity of the measurements as well as to data corruption modeled by the heavy-tailed distributions. Moreover, this estimator has low computational complexity. Our results are expressed in the form of exponential concentration inequalities for the error of the proposed estimator. On the technical side, our proofs rely on the generic chaining methods, and illustrate the power of this approach for statistical applications. Theory is supported by numerical experiments demonstrating that our estimator outperforms existing alternatives when data is heavy-tailed.