J. N. Laska and R. G. Baraniuk, "Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing," to appear in IEEE Transactions on Signal Processing, 2012.

Abstract:  The recently introduced compressive sensing (CS) framework enables digital signal acquisition systems to take advantage of signal structures beyond bandlimitedness.  Indeed, the number of CS measurements required for stable reconstruction is closer to the order of the signal complexity than the Nyquist rate.  To date, the CS theory has focused on real-valued measurements, but in practice, measurements are mapped to bits from a finite alphabet.  Moreover, in many potential applications the total number of measurement bits is constrained, which suggests a tradeoff between the number of measurements and the number of bits per measurement.  We study this situation in this paper and show that there exist two distinct regimes of operation that correspond to high/low signal-to-noise ratio (SNR).  In the measurement compression (MC) regime, a high SNR favors acquiring fewer measurements with more bits per measurement; in the quantization compression (QC) regime, a low SNR favors acquiring more measurements with fewer bits per measurement.  A surprise from our analysis and experiments is that in many practical applications it is better to operate in the QC regime, even acquiring as few as 1 bit per measurement.

Regime change in action:  Consider the CS acquisition of a length N=1000 signal that is K=10 sparse subject to the fixed bit budget B=MB, where M is the number of measurements and B is the number of bits per measurement. In each experiment, we varied the input SNR (ISNR) between 5dB and 45dB and searched for the (M,B) pair that maximized the reconstruction SNR given (a) B=N, (b) B=2N, (c) B=5N.  The solid line (blue) corresponds to the number of measurements M, while the dashed line (green) corresponds to the bit-depth B.  The left side of each plot corresponds to the QC regime, while the right side corresponds to the MC regime. In each plot there is a sharp transition between optimal bit-depth being high (B>5) and and low (B<2).  Moreover, for moderate to low ISNR, the best performance is achieved by taking just 1 bit per measurement.

A. C. Sankaranarayanan, C. Hegde, S. Nagaraj, and R. G. Baraniuk, "Go with the flow: Optical flow-based transport operators for image manifolds," Allerton Conference on Communication, Control and Computing, Allerton, IL, USA, September, 2011.

S. Nagaraj, A. C. Sankaranarayanan, and R. G. Baraniuk, "A Theory for Optical Flow-based Transport on Image Manifolds," preprint, November, 2011.

Abstract:  Image articulation manifolds (IAMs) play a central conceptual role in a host of computer vision and image understanding problems. The core premise is that we can view a collection of images, each of which is indexed by a small number of degrees of freedom (3D camera pose, motion/deformation, etc.), as a low-dimensional nonlinear manifold. In order to perform parameter estimation and navigation on an IAM, we require a transport operator that traverses the manifold from image to image. The two current approaches to manifold transport suffer from major shortcomings that have limited the practical impact of manifold methods. First, algebraic methods require that the IAM possess an unrealistic algebraic structure. Second, locally linear methods based on a tangent plane approximation cannot cope with the non-differentiability of IAMs containing images with sharp edges. In this paper, we demonstrate that the optical flow between pairs of images on an IAM is a valid transport operator with a number of attractive properties. In particular, we establish that the optical flow forms a low-dimensional smooth manifold. Several experiments involving novel-view synthesis, geometric clustering, and manifold charting validate that the optical flow manifold approach both offers performance significantly superior to current approaches and is practical for real-world applications.

An example from the paper illustrating the efficacy of OFM based image synthesis.  We compare classical locally linear modeling of an IAM versus optical flow-based transport for synthesizing new images on an IAM. We aim to synthesize images on the IAM that lie "between" two given input images. The non-differentiability of IAMs cannot be accurately captured by locally linear tangent spaces and transport; hence the corresponding synthesized images exhibit severe blurring and cross-fading artifacts. In contrast, optical flow-based transport results in sharp, realistic images.  (Click on the image to zoom in.)

Another example from the paper illustrating the efficacy of OFM based manifold learning.  We generated an IAM by cropping 200x200 pixel patches at random from a larger image, thereby generating a 2D translation manifold. (a) Sample images from the IAM showing several images at various translations. (b) Sampling of the
parameter space. 2D embeddings obtained on (c) the IAM vs. (d) the OFM. Note the near perfect isometry to the parameter space in (d).

Connexions is one of six winners of a 2011 World Innovation Summit for Education (WISE) award presented by the Qatar Foundation.  The annual WISE award recognizes "innovative educational projects from around the world."  This year's theme was "Transforming Education: Investment, Innovation and Inclusion."  Connexions, one of the first repositories of free, open-source textbooks via the Web was founded in 1999.  Connexions is among the world's largest open-education platforms; it makes available more than 19,000 modules (textbooks, lessons) used by more than 2 million people each month.

Connexions Director and Founder Richard Baraniuk plans to attend the WISE Summit 1-3 November 2011 in Doha, Qatar.  Previous award winners have included academics like MIT OpenCourseWare and nongovernmental organizations like Smallholder Farm Rural Radio in Nigeria.

M. F. Duarte and R. G. Baraniuk, "Spectral Compressive Sensing," preprint, 2011.

Abstract:  Compressive sensing (CS) is a new approach to simultaneous sensing and compression of sparse and compressible signals based on randomized dimensionality reduction. To recover a signal from its compressive measurements, standard CS algorithms seek the sparsest signal in some discrete basis or frame that agrees with the measurements. A great many applications feature smooth or modulated signals that are frequency sparse and can be modeled as a superposition of a small number of sinusoids. Unfortunately, such signals are only sparse in the discrete Fourier transform (DFT) domain when the sinusoid frequencies live precisely at the center of the DFT bins. When this is not the case, CS recovery performance degrades significantly. In this paper, we introduce a suite of spectral CS (SCS) recovery algorithms for arbitrary frequency sparse signals. The key ingredients are an over-sampled DFT frame, a signal model that inhibits closely spaced sinusoids, and classical sinusoid parameter estimation algorithms from the field of spectral estimation. Using periodogram and line spectral estimation methods (specifically Thomson’s multitaper method and root MUSIC), we demonstrate that SCS recovery significantly outperforms current state-of-the-art CS algorithms based on the DFT while providing provable bounds on the number of measurements required for stable recovery.

An example from the paper (Figure 3) illustrating the efficacy of SCS.  Experimental setup:  M = 300 noiseless random measurements of a signal of length N = 1024 composed of K = 20 complex-valued sinusoids with arbitrary real-valued frequencies. We compare the frequency spectra obtained from redundant periodograms of (a) the original signal and its recovery using (b) root MUSIC on M signal samples (SNR = 0.65dB), (c) standard CS using the orthonormal DFT basis (SNR = 5.3dB), (d) standard CS using a 10x zero-padded, redundant DFT frame (SNR = -4.4dB), (e) SCS using Algorithm 1 from the paper (SNR = 23.8dB), and (f) SCS using Algorithm 3 from the paper (SNR = 23.6dB). A software toolbox for SCS is available here.

C. Studer and R. G. Baraniuk, "Stable Restoration and Separation of Approximately Sparse Signals," preprint, 2011.

Abstract: This paper develops new theory and algorithms to recover signals that are approximately sparse in some general (i.e., basis, frame, over-complete, or incomplete)
dictionary but corrupted by a combination of measurement noise and interference having a sparse representation in a second general dictionary. Particular applications covered by our framework include the restoration of signals impaired by impulse noise, narrowband interference, or saturation, as well as image in-painting, super-resolution, and signal separation. We develop efficient recovery algorithms and deterministic conditions that guarantee stable restoration and separation. Two application examples demonstrate
the efficacy of our approach.

An example from the paper (Figure 3) showing the restoration of a scratched photograph.  Clockwise from upper left: original image; scratched image; blind scratch removal that has no access to the scratch locations; scratch removal that has access to the scratch locations.

Back by popular demand!
Get your cryptic and cool, JPS- designed, CS t-shirt, mug, etc. at

www.cafepress.com/sigproc

M. A. Davenport, J. N. Laska, J. R. Treichler, and R. G. Baraniuk, "The Pros and Cons of Compressive Sensing for Wideband Signal Acquisition: Noise Folding vs. Dynamic Range," preprint, April 2011

Abstract: Compressive sensing (CS) exploits the sparsity present in many common signals to reduce the number of measurements needed for digital acquisition. With this reduction would come, in theory, commensurate reductions in the size, weight, power consumption, and/or monetary cost of both signal sensors and any associated communication links. This paper examines the use of CS in the design of a wideband radio receiver in a noisy environment. We formulate the problem statement for such a receiver and establish a reasonable set of requirements that a receiver should meet to be practically useful. We then evaluate the performance of a CS-based receiver in two ways: via a theoretical analysis of the expected performance, with a particular emphasis on noise and dynamic range, and via simulations that compare the CS receiver against the performance expected from a conventional implementation. On the one hand, we show that CS-based systems that aim to reduce the number of acquired measurements are somewhat sensitive to signal noise, exhibiting a 3dB SNR loss per octave of subsampling which parallels the classic noise-folding phenomenon. On the other hand, we demonstrate that since they sample at a lower rate, CS-based systems can potentially attain a significantly larger dynamic range. Hence, we conclude that while a CS-based system has inherent limitations that do impose some restrictions on its potential applications, it also has attributes that make it highly desirable in a number of important practical settings.

This paper builds on our initial analysis of the "3dB/octave" effect in J. R. Treichler, M. A. Davenport, and R. G. Baraniuk,"Application of compressive sensing to the design of wideband signal acquisition receivers", 6th U.S. / Australia Joint Workshop on Defense Applications of Signal Processing (DASP), Lihue, Hawaii, Sept., 2009.

Our key findings are summarized in two experiments (Figure 3 from the paper).  We take M randomized measurements of length N sparse signals and define the subsampling ratio as ρ = N/M.  Con: The top figure shows that the SNR of a CS reconstruction degrades by 3dB per octave of subsampling when the signal is corrupted by signal noise (and not just the measurement noise that has been the focus of the CS literature to date). This noise folding effect is characteristic of other, more classical subsampling schemes like bandpass sampling.  Pro: As the subsampling ratio increases, a CS acquisition system can employ a higher-resolution quantizer and thus offer a larger dynamic range than a conventional ADC-based system. The bottom figure shows that, for the signals under consideration in the simulation, the dynamic range gain grows by as much as 5dB per octave of subsampling. Hence, there is a regime where CS acquisition significantly outperforms conventional ADC-based acquisition.

L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk, "Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors", preprint, 15 April 2011.

Abstract: 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 a large class of measurement mappings achieve this optimal bound.  Second, we consider reconstruction robustness to measurement errors and noise and introduce the Binary ε-Stable Embedding (BεSE) property, which characterizes the robustness measurement process to sign changes.  We show the same class of matrices that provide optimal noiseless performance also enable such a robust mapping.  On the practical side, we introduce the Binary Iterative Hard Thresholding (BIHT) algorithm for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.

An evocative result (Figure 8 from the paper): 1-bit CS outperforms conventional Nyquist sampling when bits are at a premium.  The figure compares the performance of several different flavors of Nyquist rate sampling using B bits per measurement vs. 1-bit CS at B times the Nyquist rate (red line). The total number of measurement bits is the same for all samplers.  The figure indicates that 1-bit CS significantly outperforms the more conventional approaches when B<6.

R. G. Baraniuk, "More Is Less: Signal Processing and the Data Deluge", Science, vol. 331, no. 6018, pp. 717-719, Feb, 2011.

Abstract:  The data deluge is changing the operating environment of many sensing systems from data-poor to data-rich––so data-rich that we are in jeopardy of being overwhelmed. Managing and exploiting the data deluge require a reinvention of sensor system design and signal processing theory. The potential pay-offs are huge, as the resulting sensor systems will enable radically new information technologies and powerful new tools for scientific discovery.

We've officially launched the Learning Machines Laboratory, our effort at Rice to develop a personalized learning system that integrates text, video, simulations, problems, feedback hints, and tutoring and optimizes the learning experience based on each user’s background, context, and learning goals.

We're very excited to be working with two top-notch cognitive psychologists on the project, Prof. Elizabeth Marsh and Dr. Andrew Butler, both of Duke University.  The beta PLS system is being deployed and tested at Rice University in Fall 2011.