Differential imaging is a technique to post-process images captured by ground-based telescopes during an observation campaign, in order to make exoplanets in a distant planetary system directly visible and to remove the so-called quasi-static speckles that dramatically affect detection capabilities.In order to introduce geometric diversity between the exoplanets and the quasi-static speckles, the light is split into spectral channels during the data acquisition process, producing a 4-D data cube with images recorded at many wavelengths and at many times.In this work, we propose to follow an inverse problem approach to model the astronomical data as the contribution of a low-rank component containing the background of quasi-static speckles and a sparse component containing the exoplanets.We then formulate the resulting model as a convex non-smooth optimization model so that an accelerated proximal gradient descent can be used to solve the detection problem.

Recently, many self-supervised learning methods for image reconstruction have been proposed that can learn from noisy data alone, bypassing the need for ground-truth references. Most existing methods cluster around two classes: i) Stein's Unbiased Risk Estimate (SURE) and similar approaches that assume full knowledge of the noise distribution, and ii) Noise2Self and similar cross-validation methods that require very mild knowledge about the noise distribution. The first class of methods tends to be impractical, as the noise level is often unknown in real-world applications, and the second class is often suboptimal compared to supervised learning. In this paper, we provide a theoretical framework that characterizes this expressivity-robustness trade-off and propose a new approach based on SURE, but unlike the standard SURE, does not require knowledge about the noise level. Throughout a series of experiments, we show that the proposed estimator outperforms other existing self-supervised methods on various imaging inverse problems.

Random data sketching (or projection) is now a classical technique enabling, for instance, approximate numerical linear algebra and machine learning algorithms with reduced computational complexity and memory. In this context, the possibility of performing data processing (such as pattern detection or classification) directly in the sketched domain without accessing the original data was previously achieved for linear random sketching methods and compressive sensing. In this work, we show how to estimate simple signal processing tasks (such as deducing local variations in a image) directly using random quadratic projections achieved by an optical processing unit. The same approach allows for naive data classification methods directly operated in the sketched domain. We report several experiments confirming the power of our approach.

We propose a direct imaging method for the detection of exo-planets based on a combined low-rank plus structured sparse model. For this task, we develop a dictionary of possible effective circular trajectories a planet can take during the observation time, elements of which can be efficiently computed using rotation and convolution operation. We design a simple alternating iterative hard-thresholding algorithm that jointly promotes a low-rank background and a sparse exoplanet foreground, to solve the non-convex optimisation problem. The experimental comparison on the β-Pictoris exoplanet benchmark dataset shows that our method has the potential to outperform the widely used Annular PCA for specific planet light intensities in terms of the receiver operating characteristic (ROC) curves.

Rank-one projections (ROP) of matrices and quadratic random sketching of signals support several data processing and machine learning methods, as well as recent imaging applications, such as phase retrieval or optical processing units.In this paper, we demonstrate how signal estimation can be operated directly through such quadratic sketchesequivalent to the ROPs of the "lifted signal" obtained as its outer product with itself-without explicitly reconstructing that signal.Our analysis relies on showing that, up to a minor debiasing trick, the ROP measurement operator satisfies a generalised sign product embedding (SPE) property.In a nutshell, the SPE shows that the scalar product of a signal sketch with the sign of the sketch of a given pattern approximates the square of the projection of that signal on this pattern.This thus amounts to an insertion (an inception) of a ROP model inside a ROP sketch.The effectiveness of our approach is evaluated in several synthetic experiments. * LJ is

Neural networks with random weights appear in a variety of machine learning applications, most prominently as the initialization of many deep learning algorithms and as a computationally cheap alternative to fully learned neural networks. In the present article, we enhance the theoretical understanding of random neural networks by addressing the following data separation problem: under what conditions can a random neural network make two classes $\mathcal{X}^-, \mathcal{X}^+ \subset \mathbb{R}^d$ (with positive distance) linearly separable? We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. Crucially, the number of required neurons is explicitly linked to geometric properties of the underlying sets $\mathcal{X}^-, \mathcal{X}^+$ and their mutual arrangement. This instance-specific viewpoint allows us to overcome the usual curse of dimensionality (exponential width of the layers) in non-pathological situations where the data carries low-complexity structure. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity (based on a localized version of Gaussian mean width), which leads to sound and informative separation guarantees. We connect our result with related lines of work on approximation, memorization, and generalization.

Fluorescence imaging through ultrathin fibers is a promising approach to obtain high-resolution imaging with molecular specificity at depths much larger than the scattering mean-free paths of biological tissues. Such imaging techniques, generally termed lensless endoscopy, rely upon the wavefront control at the distal end of a fiber to coherently combine multiple spatial modes of a multicore (MCF) or multimode fiber (MMF). Typically, a spatial light modulator (SLM) is employed to combine hundreds of modes by phase-matching to generate a high-intensity focal spot. This spot is subsequently scanned across the sample to obtain an image. We propose here a novel scanning scheme, partial speckle scanning (PSS), inspired by compressive sensing theory, that avoids the use of an SLM to perform fluorescent imaging with optical fibers with reduced acquisition time. Such a strategy avoids photo-bleaching while keeping high reconstruction quality. We develop our approach on two key properties of the MCF: (i) the ability to easily generate speckles, and (ii) the memory effect that allows one to use fast scan mirrors to shift light patterns. First, we show that speckles are subexponential random fields. Despite their granular structure, an appropriate choice of the reconstruction parameters makes them good candidates to build efficient sensing matrices. Then, we numerically validate our approach and apply it on experimental data. The proposed sensing technique outperforms conventional raster scanning: higher reconstruction quality is achieved with far fewer observations. For a fixed reconstruction quality, our speckle scanning approach is faster than compressive sensing schemes which require changing the speckle pattern for each observation.

In this paper, we investigate the application of continuous sparse signal reconstruction algorithms for the estimation of the ranges and speeds of multiple moving targets using an FMCW radar. Conventionally, to be reconstructed, continuous sparse signals are approximated by a discrete representation. This discretization of the signal’s parameter domain leads to mismatches with the actual signal. While increasing the grid density mitigates these errors, it dramatically increases the algorithmic complexity of the reconstruction. To overcome this issue, we propose a fast greedy algorithm for off-the-grid detection of multiple moving targets. This algorithm extends existing continuous greedy algorithms to the framework of factorized sparse representations of the signals. This factorized representation is obtained from simplifications of the radar signal model which, up to a model mismatch, strongly reduces the dimensionality of the problem. Monte-Carlo simulations of a K-band radar system validate the ability of our method to produce more accurate estimations with less computation time than the on-the-grid methods and than methods based on non-factorized representations.

We consider the question of estimating a real low-complexity signal (such as a sparse vector or a low-rank matrix) from the phase of complex random measurements. We show that in this phase-only compressive sensing (PO-CS) scenario, we can perfectly recover such a signal with high probability and up to global unknown amplitude if the sensing matrix is a complex Gaussian random matrix and the number of measurements is large compared to the complexity level of the signal space. Our approach proceeds by recasting the (non-linear) PO-CS scheme as a linear compressive sensing model built from a signal normalization constraint, and a phase-consistency constraint imposing any signal estimate to match the observed phases in the measurement domain. Practically, stable and robust estimation of the signal direction is achieved from any instance optimal algorithm of the compressive sensing literature (such as basis pursuit denoising). This is ensured by proving that the matrix associated with this equivalent linear model satisfies with high probability the restricted isometry property under the above condition on the number of measurements. We finally observe experimentally that robust signal direction recovery is reached at about twice the number of measurements needed for signal recovery in compressive sensing.

This letter analyzes the performances of a simple reconstruction method, namely the Projected Back-Projection (PBP), for estimating the direction of a sparse signal from its phase-only (or amplitude-less) complex Gaussian random measurements, i.e., an extension of one-bit compressive sensing to the complex field. To study the performances of this algorithm, we show that complex Gaussian random matrices respect, with high probability, a variant of the Restricted Isometry Property (RIP) relating to the ℓ1-norm of the sparse signal measurements to their ℓ2-norm. This property allows us to upper-bound the reconstruction error of PBP in the presence of phase noise. Monte Carlo simulations are performed to highlight the performance of our approach in this phase-only acquisition model when compared to error achieved by PBP in classical compressive sensing.

We investigate the problems of 1-D and 2-D signal recovery from subsampled Hadamard measurements using Haar wavelet as a sparsity inducing prior. These problems are of interest in, e.g., computational imaging applications relying on optical multiplexing or single-pixel imaging. However, the realization of such modalities is often hindered by the coherence between the Hadamard and Haar bases. The variable and multilevel density sampling strategies solve this issue by adjusting the subsampling process to the local and multilevel coherence, respectively, between the two bases; hence enabling successful signal recovery. In this work, we compute an explicit sample-complexity bound for Hadamard-Haar systems as well as uniform and non-uniform recovery guarantees; a seemingly missing result in the related literature. We explore the faithfulness of the numerical simulations to the theoretical results and show in a practically relevant instance, e.g., single-pixel camera, that the target signal can be recovered from a few Hadamard measurements.

Single Pixel (SP) imaging is now a reality in many applications, e.g., biomedical ultrathin endoscope and fluorescent spectroscopy. In this context, many schemes exist to improve the light throughput of these device, e.g., using structured illumination driven by compressive sensing theory. In this work, we consider the combination of SP imaging with Fourier Transform Interferometry (SP-FTI) to reach high-resolution HyperSpectral (HS) imaging, as desirable, e.g., in fluorescent spectroscopy. While this association is not new, we here focus on optimizing the spatial illumination, structured as Hadamard patterns, during the optical path progression. We follow a variable density sampling strategy for space-time coding of the light illumination, and show theoretically and numerically that this scheme allows us to reduce the number of measurements and light-exposure of the observed object compared to conventional compressive SP-FTI.

This work addresses the problem of learning from large collections of data with privacy guarantees. The sketched learning framework proposes to deal with the large scale of datasets by compressing them into a single vector of generalized random moments, from which the learning task is then performed. We modify the standard sketching mechanism to provide differential privacy, using addition of Laplace noise combined with a subsampling mechanism (each moment is computed from a subset of the dataset). The data can be divided between several sensors, each applying the privacy-preserving mechanism locally, yielding a differentially-private sketch of the whole dataset when reunited. We apply this framework to the k-means clustering problem, for which a measure of utility of the mechanism in terms of a signal-to-noise ratio is provided, and discuss the obtained privacy-utility tradeoff.

This paper presents a new compressive sensing acquisition scheme well adapted for highly constrained hardware implementations. The proposed sensing model being basically designed to meet both theoretical (i.e., Restricted Isometry Property) and hardware requirements (i.e., power consumption, silicon footprint), is highly suitable for image sensors applications addressing both image rendering and embedded decision making tasks. In fact, for a pixels array, the proposed framework consists in applying for each row a random modulation ±1 and a random permutation of the pixels, and then averaging the outputs by column to extract a compressed vector. This model is shown to be relevant as it has the same theoretical performance as a randomly generated sensing scheme as well as a low silicon footprint for physical implementation. Various numerical results and a discussion on possible implementations will be presented to show the robustness and the efficiency of the proposed model.

This work presents a compact VGA (480 × 640) CMOS Image Sensor (CIS) architecture with dedicated end-of-column Compressive Sensing (CS) scheme allowing embedded object recognition. The architecture takes advantage of a low-footprint pseudo-random data mixing circuit and a first order incremental Sigma-Delta (ΣΔ) Analog to Digital Converter (ADC) to extract compressed features. The proposed CIS achieves an object recognition accuracy of ≃ 93% on the Georgia Tech face recognition database (GIT, 10 classes out of 50) thanks to a linear Support Vector Machine (SVM) classifier implemented by an optimized Digital Signal Processing (DSP). We stress that the signal independent dimensionality reduction performed by our dedicated CS scheme (1/480) allows to dramatically reduce memory requirements (≈ 32 kbit) related -in our case- to the ex-situ learned affine function of the linear SVM.

This paper explores hierarchical clustering methods to learn a hierarchical multi-class classifier on compressed measurements in the context of highly constrained hardware (e.g., always-on ultra low power vision systems). In contrast to the popular multi-class classification approaches based on multiple binary classifiers (i.e., one-vs.-all and one-vs.one [1]), a hierarchical classifier requires only O(log2C) binary classifiers in a decision tree. In this work, we investigate three clustering methods used to construct balanced clusters at each node thus reducing the depth of the decision tree in order to lower hardware requirements to its minimum. A binary Support Vector Machine (SVM) [2] classifier is then learned on Compressive Sensing measurements [3] at each node of the hierarchical tree. Our results, based on two object recognition databases (AT&T and COIL-100 databases), show the competitiveness of hierarchical classification in terms of hardware requirements (lower memory and computational complexity) as well as its classification accuracy.

Fourier transform interferometry (FTI) is an appealing hyperspectral (HS) imaging modality for many applications demanding high spectral resolution, e.g., in fluorescence microscopy. However, the effective resolution of FTI is limited by the durability of biological elements when exposed to illuminating light. Overexposed elements are indeed subject to photo-bleaching and become unable to fluoresce. In this context, the acquisition of biological HS volumes based on sampling the optical path difference axis at Nyquist rate leads to unpleasant trade-offs between spectral resolution, quality of the HS volume, and light exposure intensity. In this paper we propose two variants of the FTI imager, i.e., coded illumination-FTI (CI-FTI) and structured illumination FTI (SI-FTI), based on the theory of compressive sensing (CS). These schemes efficiently modulate light exposure temporally (in CI-FTI) or spatiotemporally (in SI-FTI). Leveraging a variable density sampling strategy recently introduced in CS, we provide near-optimal illumination strategies, so that the light exposure imposed on a biological specimen is minimized while the spectral resolution is preserved. Our theoretical analysis focuses on two criteria: (i) a trade-off between exposure intensity and the quality of the reconstructed HS volume for a given spectral resolution; (ii) maximizing HS volume quality for a fixed spectral resolution and constrained light exposure budget. Our contributions can be adapted to an FTI imager without hardware modifications. The reconstruction of HS volumes from CS FTI measurements relies on an $\ell_1$-norm minimization problem promoting a spatiospectral sparsity prior. Numerically, we support the proposed methods on synthetic data and simulated CS measurements (from actual FTI measurements) under various scenarios. In particular, the biological HS volumes considered in this work can be reconstructed with a three-to-tenfold reduction in the light exposure.

Fourier Transform Interferometry (FTI) is an interferometric procedure for acquiring HyperSpectral (HS) data. Recently, it has been observed that the light source highlighting a (biologic) sample can be coded before the FTI acquisition in a procedure called Coded Illumination-FTI (CI-FTI). This turns HS data reconstruction into a Compressive Sensing (CS) problem regularized by the sparsity of the HS data. CI-FTI combines the high spectral resolution of FTI with the advantages of reduced-light-exposure imaging in biology. In this paper, we leverage multilevel sampling scheme recently developed in CS theory to adapt the coding strategy of CI-FTI to the spectral sparsity structure of HS data in Fluorescence Spectroscopy (FS). This structure is actually extracted from the spectral signatures of actual fluorescent dyes used in FS. Accordingly, the optimum illumination coding as well as the theoretical recovery guarantee are derived. We conduct numerous numerical experiments on synthetic and experimental data that show the faithfulness of the proposed theory to experimental observations.

The recent framework of compressive statistical learning proposes to design tractable learning algorithms that use only a heavily compressed representation - or sketch - of massive datasets. Compressive K-Means (CKM) is such a method: It aims at estimating the centroids of data clusters from pooled, nonlinear, and random signatures of the learning examples. While this approach significantly reduces computational time on very large datasets, its digital implementation wastes acquisition resources because the learning examples are compressed only after the sensing stage. The present work generalizes the CKM sketching procedure to a large class of periodic nonlinearities including hardware-friendly implementations that compressively acquire entire datasets. This idea is exemplified in a quantized CKM procedure, a variant of CKM that leverages 1-bit universal quantization (i.e., retaining the least significant bit of a standard uniform quantizer) as the periodic sketch nonlinearity. Trading for this resource-efficient signature (standard in most acquisition schemes) has almost no impact on the clustering performance, as illustrated by numerical experiments.

The realisation of sensing modalities based on the principles of compressed sensing is often hindered by discrepancies between the mathematical model of its sensing operator, which is necessary during signal recovery, and its actual physical implementation, which can amply differ from the assumed model. In this paper we tackle the bilinear inverse problem of recovering a sparse input signal and some unknown, unstructured multiplicative factors affecting the sensors that capture each compressive measurement. Our methodology relies on collecting a few snapshots under new draws of the sensing operator, and applying a greedy algorithm based on projected gradient descent and the principles of iterative hard thresholding. We explore empirically the sample complexity requirements of this algorithm by testing its phase transition, and show in a practically relevant instance of this problem for compressive imaging that the exact solution can be obtained with only a few snapshots.

Given a set of detections, detected at each time instant independently, we investigate how to associate them across time. This is done by propagating labels on a set of graphs, each graph capturing how either the spatio-temporal or the appearance cues promote the assignment of identical or distinct labels to a pair of detections. The graph construction is motivated by a locally linear embedding of the detection features. Interestingly, the neighborhood of a node in appearance graph is defined to include all the nodes for which the appearance feature is available (even if they are temporally distant). This gives our framework the uncommon ability to exploit the appearance features that are available only sporadically. Once the graphs have been defined, multi-object tracking is formulated as the problem of finding a label assignment that is consistent with the constraints captured each graph, which results into a difference of convex (DC) program. We propose to decompose the global objective function into node-wise sub-problems. This not only allows a computationally efficient solution, but also supports an incremental and scalable construction of the graph, thereby making the framework applicable to large graphs and practical tracking scenarios. Moreover, it opens the possibility of parallel implementation.

Under which conditions and with which distortions can we preserve the pairwise distances of low-complexity vectors, e.g., for structured sets, such as the set of sparse vectors or the one of low-rank matrices, when these are mapped (or embedded) in a finite set of vectors? This work addresses this general question through the specific use of a quantized and dithered random linear mapping, which combines, in the following order, a subGaussian random projection in RMof vectors in RN, a random translation, or dither, of the projected vectors, and a uniform scalar quantizer of resolution δ > 0 applied componentwise. Thanks to this quantized mapping, we are first able to show that, with high probability, an embedding of a bounded set K ⊂ RNin δZMcan be achieved when distances in the quantized and in the original domains are measured with the l1- and l2-norm, respectively, and provided the number of quantized observations M is large before the square of the “Gaussian mean width” of K. In this case, we show that the embedding is actually quasi-isometric and only suffers from both multiplicative and additive distortions whose magnitudes decrease as M-1/5for general sets, and as M-1/2for structured set, when M increases. Second, when one is only interested in characterizing the maximal distance separating two elements of K mapped to the same quantized vector, i.e., the “consistency width” of the mapping, we show that for a similar number of measurements and with high probability, this width decays as M-1/4for general sets and as 1/M for structured ones when M increases. Finally, as an important aspect of this paper, we also establish how the non-Gaussianity of sub-Gaussian random projections inserted in the quantized mapping (e.g., for Bernoulli random matrices) impacts the class of vectors that can be embedded or whose consistency width provably decays when M increases.

The progress in imaging techniques have allowed the study of various aspect of cellular mechanisms. To isolate individual cells in live imaging data, we introduce an elegant image segmentation framework that effectively extracts cell boundaries, even in the presence of poor edge details. Our approach works in two stages. First, we estimate pixel interior/border/exterior class probabilities using random ferns. Then, we use an energy minimization framework to compute boundaries whose localization is compliant with the pixel class probabilities. We validate our approach on a manually annotated dataset.

In this paper, we study the support recovery guarantees of underdetermined sparse regression using the $\ell_1$-norm as a regularizer and a non-smooth loss function for data fidelity. More precisely, we focus in detail on the cases of $\ell_1$ and $\ell_\infty$ losses, and contrast them with the usual $\ell_2$ loss.While these losses are routinely used to account for either sparse ($\ell_1$ loss) or uniform ($\ell_\infty$ loss) noise models, a theoretical analysis of their performance is still lacking. In this article, we extend the existing theory from the smooth $\ell_2$ case to these non-smooth cases. We derive a sharp condition which ensures that the support of the vector to recover is stable to small additive noise in the observations, as long as the loss constraint size is tuned proportionally to the noise level. A distinctive feature of our theory is that it also explains what happens when the support is unstable. While the support is not stable anymore, we identify an "extended support" and show that this extended support is stable to small additive noise. To exemplify the usefulness of our theory, we give a detailed numerical analysis of the support stability/instability of compressed sensing recovery with these different losses. This highlights different parameter regimes, ranging from total support stability to progressively increasing support instability.

Several exact recovery criteria (ERC) ensuring that orthogonal matching pursuit (OMP) identifies the correct support of sparse signals have been developed in the last few years. These ERC rely on the restricted isometry property (RIP), the associated restricted isometry constant (RIC) and sometimes the restricted orthogonality constant (ROC). In this paper, three of the most recent ERC for OMP are examined. The contribution is to show that these ERC remain valid for a generalization of OMP, entitled simultaneous orthogonal matching pursuit (SOMP), that is capable to process several measurement vectors simultaneously and return a common support estimate for the underlying sparse vectors. The sharpness of the bounds is also briefly discussed in light of previous works focusing on OMP.

The simultaneous orthogonal matching pursuit (SOMP) algorithm aims to find the joint support of a set of sparse signals acquired under a multiple measurement vector model. Critically, the analysis of SOMP depends on the maximal inner product of any atom of a suitable dictionary and the current signal residual, which is formed by the subtraction of previously selected atoms. This inner product, or correlation, is a key metric to determine the best atom to pick at each iteration. This letter provides, for each iteration of SOMP, a novel lower bound of the aforementioned metric for the atoms belonging to the correct and common joint support of the multiple signals. Although the bound is obtained for the noiseless case, its main purpose is to intervene in noisy analyses of SOMP. Finally, it is shown for specific signal patterns that the proposed bound outperforms state-of-the-art results for SOMP and orthogonal matching pursuit (OMP) as a special case.

This letter focuses on the estimation of low-complexity signals when they are observed through$M$uniformly quantized compressive observations. Among such signals, we consider 1-D sparse vectors, low-rank matrices, or compressible signals that are well approximated by one of these two models. In this context, we prove the estimation efficiency of a variant of Basis Pursuit Denoise, called Consistent Basis Pursuit (CoBP), enforcing consistency between the observations and the re-observed estimate, while promoting its low-complexity nature. We show that the reconstruction error of CoBP decays like${M^{ - 1/4}}$when all parameters but$M$are fixed. Our proof is connected to recent bounds on the proximity of vectors or matrices when (i) those belong to a set of small intrinsic “dimension”, as measured by the Gaussian mean width, and (ii) they share the same quantized (dithered) random projections. By solving CoBP with a proximal algorithm, we provide some extensive numerical observations that confirm the theoretical bound as$M$is increased, displaying even faster error decay than predicted. The same phenomenon is observed in the special, yet important case of 1-bit CS.

This paper provides new error bounds on consistent reconstruction methods for signals observed from quantized random projections. Those signal estimation techniques guarantee a perfect matching between the available quantized data and a new observation of the estimated signal under the same sensing model. Focusing on dithered uniform scalar quantization of resolution δ > 0, we prove first that, given a Gaussian random frame of RNwith M vectors, the worst-case ℓ2-error of consistent signal reconstruction decays with high probability as O((N/M) log(M/√N)) uniformly for all signals of the unit ball BN⊂ RN. Up to a log factor, this matches a known lower bound in Ω(N/M) and former empirical validations in O(N/M). Equivalently, if M exceeds a minimal number of frame coefficients growing like O((N)/(ε0) log(√N)/(E0)), any vectors in BN with M identical quantized projections are at most E0apart with high probability. Second, in the context of quantized compressed sensing with M Gaussian random measurements and under the same scalar quantization scheme, consistent reconstructions of K-sparse signals of RN have a worst case error that decreases with high probability as O((K)/(M) log(MN)/(√K3)) uniformly for all such signals. Finally, we show that the proximity of vectors whose quantized random projections are only approximately consistent can still be bounded with high probability. A certain level of corruption is thus allowed in the quantization process, up to the appearance of a systematic bias in the reconstruction error of (almost) consistent signal estimates.

A recently designed hyperspectral imaging device enables multiplexed acquisition of an entire data volume in a single snapshot thanks to monolithically-integrated spectral filters. Such an agile imaging technique comes at the cost of a reduced spatial resolution and the need for a demosaicing procedure on its interleaved data. In this work, we address both issues and propose an approach inspired by recent developments in compressed sensing and analysis sparse models. We formulate our superresolution and demosaicing task as a 3-D generalized inpainting problem. Interestingly, the target spatial resolution can be adjusted for mitigating the compression level of our sensing. The reconstruction procedure uses a fast greedy method called Pseudo-inverse IHT. We also show on simulations that a random arrangement of the spectral filters on the sensor is preferable to regular mosaic layout as it improves the quality of the reconstruction. The efficiency of our technique is demonstrated through numerical experiments on both synthetic and real data as acquired by the snapshot imager.

Randomized sets of binary tests have appeared to be quite effective in solving a variety of image processing and vision problems. The exponential growth of their memory usage with the size of the sets however hampers their implementation on the memory-constrained hardware generally available on low-power embedded systems. Our paper addresses this limitation by formulating the conventional semi-naive Bayesian ensemble decision rule in terms of posterior class probabilities, instead of class conditional distributions of binary tests realizations. Subsequent clustering of the posterior class distributions computed at training allows for sharp reduction of large binary tests sets memory footprint, while preserving their high accuracy. Our validation considers a smart metering applicative scenario, and demonstrates that up to 80% of the memory usage can be saved, at constant accuracy.

Light rays incident on a transparent object of uniform refractive index undergo deflections, which uniquely characterize the surface geometry of the object. Associated with each point on the surface is a deflection map (or spectrum) which describes the pattern of deflections in various directions. This article presents a novel method to efficiently acquire and reconstruct sparse deflection spectra induced by smooth object surfaces. To this end, we leverage the framework of compressed sensing (CS) in a particular implementation of a schlieren deflectometer, i.e., an optical system providing linear measurements of deflection spectra with programmable spatial light modulation patterns. In particular, we design those modulation patterns on the principle of spread spectrum CS for reducing the number of observations. Interestingly, the ability of our device to simultaneously observe the deflection spectra on a dense discretization of the object surface is related to a particular multiple measurement vector model. This scheme allows us to estimate both the noise power and the instrumental point spread function in a specific calibration procedure. We formulate the spectrum reconstruction task as the solving of a linear inverse problem regularized by an analysis sparsity prior which uses a translation invariant wavelet frame. Our results demonstrate the capability and advantages of using a CS-based approach for deflectometric imaging both on simulated data and experimental deflectometric data. Finally, the paper presents an extension of our method showing how we can extract the main deflection direction in each point of the object surface from a few compressive measurements, without needing any costly reconstruction procedures. This compressive characterization is then confirmed with experimental results on simple plano-convex and multifocal intraocular lenses studying the evolution of the main deflection as a function of the object point location.

In 1733, Georges-Louis Leclerc, Comte de Buffon in France, set the ground of geometric probability theory by defining an enlightening problem: what is the probability that a needle thrown randomly on a ground made of equispaced parallel strips lies on two of them? In this paper, we show that the solution to this problem, and its generalization to N dimensions, allows us to discover a quantized form of the Johnson-Lindenstrauss (JL) lemma, i.e., one that combines a linear dimensionality reduction procedure with a uniform quantization of precision δ > 0. In particular, given a finite set S ⊂ ℝNof S points and a distortion level ϵ > 0, as soon as M > M0= O(ϵ-2log S), we can (randomly) construct a mapping from (S, ℓ2) to (δℤM, ℓ1) that approximately preserves the pairwise distances between the points of S. Interestingly, compared with the common JL lemma, the mapping is quasi-isometric and we observe both an additive and a multiplicative distortions on the embedded distances. These two distortions, however, decay as O((log S/M)1/2) when M increases. Moreover, for coarse quantization, i.e., for high δ compared with the set radius, the distortion is mainly additive, while for small δ we tend to a Lipschitz isometric embedding. Finally, we prove the existence of a nearly quasi-isometric embedding of (S, ℓ2) into (δℤM, ℓ2). This one involves a non-linear distortion of the ℓ2-distance in S that vanishes for distant points in this set. Noticeably, the additive distortion in this case is slower, and decays as O((log S/M)1/4).

It is well-known that the performance of the Gaussian Mixture Model (GMM) based Acoustic-to-Articulatory Inversion (AAI) improves by either incorporating smoothness constraint directly in the inversion criterion or smoothing (low-pass filtering) estimated articulator trajectories in a post-processing step, where smoothing is performed independently of the inversion. As the low-pass filtering is independent of inversion, the smoothed articulator trajectory samples no longer remain optimal as per the inversion criterion. In this work, we propose a sparse smoothing technique which constrains the smoothed articulator trajectory to be different from the estimated trajectory only at a sparse subset of samples while simultaneously achieving the required degree of smoothness. Inversion experiments on the articulatory database show that the sparse smoothing achieves an AAI performance similar to that using low-pass filtering but in sparse smoothing ~15% (on average) of the samples in the smoothed articulator trajectory remain identical to those in the estimated articulator trajectory thereby preserve their AAI optimality as opposed to 0% in low-pass filtering.

The 2-D phase unwrapping problem aims at retrieving a “phase” image from its modulo 2π observations. Many applications, such as interferometry or synthetic aperture radar imaging, are concerned by this problem since they proceed by recording complex or modulated data from which a “wrapped” phase is extracted. Although 1-D phase unwrapping is trivial, a challenge remains in higher dimensions to overcome two common problems: noise and discontinuities in the true phase image. In contrast to state-of-the-art techniques, this work aims at simultaneously unwrap and denoise the phase image. We propose a robust convex optimization approach that enforces data fidelity constraints expressed in the corrupted phase derivative domain while promoting a sparse phase prior. The resulting optimization problem is solved by the Chambolle-Pock primal-dual scheme. We show that under different observation noise levels, our approach compares favorably to those that perform the unwrapping and denoising in two separate steps.

Local Binary Descriptors are becoming more and more popular for image matching tasks, especially when going mobile. While they are extensively studied in this context, their ability to carry enough information in order to infer the original image is seldom addressed. In this work, we leverage an inverse problem approach to show that it is possible to directly reconstruct the image content from Local Binary Descriptors. This process relies on very broad assumptions besides the knowledge of the pattern of the descriptor at hand. This generalizes previous results that required either a prior learning database or non-binarized features. Furthermore, our reconstruction scheme reveals differences in the way different Local Binary Descriptors capture and encode image information. Hence, the potential applications of our work are multiple, ranging from privacy issues caused by eavesdropping image keypoints streamed by mobile devices to the design of better descriptors through the visualization and the analysis of their geometric content.

Clipping or saturation in audio signals is a very common problem in signal processing, for which, in the severe case, there is still no satisfactory solution. In such case, there is a tremendous loss of information, and traditional methods fail to appropriately recover the signal. We propose a novel approach for this signal restoration problem based on the framework of Iterative Hard Thresholding. This approach, which enforces the consistency of the reconstructed signal with the clipped observations, shows superior performance in comparison to the state-of-the-art declipping algorithms. This is confirmed on synthetic and on actual high-dimensional audio data processing, both on SNR and on subjective user listening evaluations.

Schlieren deflectometry aims at characterizing the deflections undergone by refracted incident light rays at any surface point of a transparent object. For smooth surfaces, each surface location is actually associated with a sparse deflection map (or spectrum). This paper presents a novel method to compressively acquire and reconstruct such spectra. This is achieved by altering the way deflection information is captured in a common Schlieren Deflectometer, i.e., the deflection spectra are indirectly observed by the principle of spread spectrum compressed sensing. These observations are realized optically using a 2-D Spatial Light Modulator (SLM) adjusted to the corresponding sensing basis and whose modulations encode the light deviation subsequently recorded by a CCD camera. The efficiency of this approach is demonstrated experimentally on the observation of few test objects. Further, using a simple parameterization of the deflection spectra we show that relevant key parameters can be directly computed using the measurements, avoiding full reconstruction.

This paper addresses the problem of stably recovering sparse or compressible signals from compressed sensing measurements that have undergone optimal nonuniform scalar quantization, i.e., minimizing the common$\ell _{2}$-norm distortion. Generally, this quantized compressed sensing (QCS) problem is solved by minimizing the$\ell _{1}$-norm constrained by the$\ell _{2}$-norm distortion. In such cases, remeasurement and quantization of the reconstructed signal do not necessarily match the initial observations, showing that the whole QCS model is not consistent. Our approach considers instead that quantization distortion more closely resembles heteroscedastic uniform noise, with variance depending on the observed quantization bin. Generalizing our previous work on uniform quantization, we show that for nonuniform quantizers described by the “compander” formalism, quantization distortion may be better characterized as having bounded weighted$\ell _{p}$-norm ($p \geqslant 2$), for a particular weighting. We develop a new reconstruction approach, termed Generalized Basis Pursuit DeNoise (GBPDN), which minimizes the$\ell _{1}$-norm of the signal to reconstruct constrained by this weighted$\ell _{p}$-norm fidelity. We prove that, for standard Gaussian sensing matrices and$K$sparse or compressible signals in$ \BBR ^{N}$with at least$\Omega ((K \log N/K)^{p/2})$measurements, i.e., under strongly oversampled QCS scenario, GBPDN is$\ell _{2}-\ell _{1}$instance optimal and stable recovers all such sparse or compressible signals. The reconstruction error decreases as$O(2^{-B}/\sqrt {p+1})$given a budget of$B$bits per measurement. This yields a reduction by a factor$\sqrt {p+1}$of the reconstruction error compared to the one produced by$\ell _{2}$-norm constrained decoders. We also propose an primal-dual proximal splitting scheme to solve the GBPDN program which is efficient for large-scale problems. Interestingly, extensive simulations testing the GBPDN effectiveness confirm the trend predicted by the theory, that the reconstruction error can indeed be reduced by increasing$p$, but this is achieved at a much less stringent oversampling regime than the one expected by the theoretical bounds. Besides the QCS scenario, we also show that GBPDN applies straightforwardly to the related case of CS measurements corrupted by heteroscedastic generalized Gaussian noise with provable reconstruction error reduction.

The compressive sensing (CS) framework aims to ease the burden on analog-to-digital converters (ADCs) by reducing the sampling rate required to acquire and stably recover sparse signals. Practical ADCs not only sample but also quantize each measurement to a finite number of bits; moreover, there is an inverse relationship between the achievable sampling rate and the bit depth. In this paper, we investigate an alternative CS approach that shifts the emphasis from the sampling rate to the number of bits per measurement. In particular, we explore the extreme case of 1-bit CS measurements, which capture just their sign. Our results come in two flavors. First, we consider ideal reconstruction from noiseless 1-bit measurements and provide a lower bound on the best achievable reconstruction error. We also demonstrate that i.i.d. random Gaussian matrices provide measurement mappings that, with overwhelming probability, achieve nearly optimal error decay. Next, we consider reconstruction robustness to measurement errors and noise and introduce the binary$\epsilon $-stable embedding property, which characterizes the robustness of the measurement process to sign changes. We show that the same class of matrices that provide almost optimal noiseless performance also enable such a robust mapping. On the practical side, we introduce the binary iterative hard thresholding algorithm for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.

Following the Compressed Sensing (CS) paradigm, this paper studies the problem of recovering sparse or compressible signals from (scalar) non-uniformly quantized measurements. We show that a simple adaptation of the Basis Pursuit De-Quantizer introduced earlier, that is, a sign sensitive weighting of their ℓp-norm fidelity constraint, yields good SNR improvements in the signal reconstruction. As a good indication of this improvement origin, we prove theoretically that a similar decoder, using a particular side-position-to-level oracle, displays a reduction of the reconstruction error when both the number of measurements and the moment p of the constraint increase. This follows the oversampling principle underlined in our previous study for uniformly quantized CS, with an additional gain provided by the non-uniform quantization. We conclude this paper by showing the efficiency of the approach on 1-D and 2-D signal examples.

Image descriptors are widely used in applications such as object recognition, pattern classification and image registration. The descriptors encode the local visual content of the image to provide a compact, robust and distinctive representation of objects. If images differ in orientation, descriptors must be rotation invariant. This paper introduces a compact rotation invariant descriptor. The approach is based on the representation of the local visual content by a graph. A function living on the graph vertices is evaluated and transformed through spectral trimming. This transform is rotation invariant and reduces the dimensionality of the descriptor. The performance of the introduced descriptor is as good as the SIFT descriptor performance, while being about ten times more compact, as shown by experiments on transmission electron microscope images.

In this paper, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQp), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed subject to a data-fidelity constraint expressed in the ℓp-norm of the residual error for 2 ≤ p ≤ ∞. We show theoretically that, (i) the reconstruction error of these new decoders is bounded if the sensing matrix satisfies an extended Restricted Isometry Property involving the Iρ norm, and (ii), for Gaussian random matrices and uniformly quantized measurements, BPDQpperformance exceeds that of BPDN by dividing the reconstruction error due to quantization by √(p + 1). This last effect happens with high probability when the number of measurements exceeds a value growing with p, i.e., in an oversampled situation compared to what is commonly required by BPDN = BPDQ2. To demonstrate the theoretical power of BPDQp, we report numerical simulations on signal and image reconstruction problems.

In this paper, we develop an adjustable Fuzzy Extractor using the Physical Unclonable Functions (PUF) obtained by a common laser engraving method to sign physical objects. In particular, a string (or helper data) is generated by XORing a binary reduction of the PUF observation with the encoding of a randomly generated key, or identifier. Since the binary reduction (or hash) relies on keeping the sign of few random projections of the observation, a measure concentration property bounds, with a controlled accuracy, the distance between two different hashes in function of this of the original images. The error correcting code used to encode the identifier stabilizes therefore both the observation noise and the hashing distortion. In a verification stage, reobserving the PUF with the helper data in hand allows one to authenticate the object if the identifier can be exactly recovered. We conclude this work by calibrating and challenging the system on a database of laser-written PUFs, balancing helper data size, that is, hashing dimensions, and system security.

A CMOS imager is presented which has the ability to perform localized compressive sensing on-chip. In-pixel convolutions of the sensed image with measurement matrices are computed in real time, and a proposed programmable two-dimensional scrambling technique guarantees the randomness of the coefficients used in successive observation. A power and area-efficient implementation architecture is presented making use of a single ADC. A 256×256 imager has been developed as a test vehicle in a 0.18μm CIS technology. Using an 11-bit ADC, a SNR of 18.6dB with a compression factor of 3.3 is achieved after reconstruction. The total power consumption of the imager is simulated at 76.7mW from a 1.8V supply voltage.

We present a CMOS imager with built-in capability to perform Compressed Sensing coding by Random Convolution. It is achieved by a shift register set in a pseudo-random configuration. It acts as a convolutive filter on the imager focal plane, the current issued from each CMOS pixel undergoing a pseudo-random redirection controlled by each component of the filter sequence. A pseudo-random triggering of the ADC reading is finally applied to complete the acquisition model. The feasibility of the imager and its robustness under noise and non-linearities have been confirmed by computer simulations, as well as the reconstruction tools supporting the Compressed Sensing theory.

In this paper we consider the problem of sampling far below the Nyquist rate signals that are sparse linear superpositions of shifts of a known, potentially wide-band, pulse. This signal model is key for applications such as Ultra Wide Band (UWB) communications or neural signal processing. Following the recently proposed Compressed Sensing methodology, we study several acquisition strategies and show that the approximations recovered via lscr1minimization are greatly enhanced if one uses Spread Spectrum modulation prior to applying random Fourier measurements. We complement our experiments with a discussion of possible hardware implementation of our technique.

This paper addresses the problem of mapping images between different vision sensors. Such a mapping could be modeled as a sampling problem that has to encompass the change of geometry between the two sensors and the specific discretization of the real scene observed by the two different imaging systems. We formulate the problem in a general framework that can be cast as a minimization regularized problem with a linear operator, that applies to any image geometry. We then focus on the particular problem of the generation of planar images from omnidirectional images, in any viewing direction and for any size and resolution. In this regularized approach, the fidelity term is expressed in the original omnicam geometry and the regularization is based on Total Variation (TV) solved here with proximal methods. Experimental results demonstrate the superiority of this approach with respect to alternative schemes based on linear interpolation or TV in-painting.

In this paper, following the Compressed Sensing (CS) paradigm, we study the problem of recovering sparse or compressible signals from uniformly quantized measurements. We present a new class of convex optimization programs, or decoders, coined Basis Pursuit DeQuantizer of moment p (BPDQp), that model the quantization distortion more faithfully than the commonly used Basis Pursuit DeNoise (BPDN) program. Our decoders proceed by minimizing the sparsity of the signal to be reconstructed while enforcing a data fidelity term of bounded ¿p-norm, for 2pdecoders outperforms that of BPDN, with reconstruction error due to quantization divided by. This reduction relies on a modified Restricted Isometry Property of the sensing matrix expressed in the ¿p-norm (RIPp); a property satisfied by Gaussian random matrices with high probability. We conclude with numerical experiments comparing BPDQpand BPDN for signal and image reconstruction problems.