OpenStax College is a nonprofit organization committed to improving student access to quality learning materials.  Today we announce the first 5 of a library of 20+ free, open-source textbooks for the highest-impact college courses: College Physics, Introduction to Sociology, Anatomy and Physiology, Biology, and Concepts in Biology.  College Physics and Introduction to Sociology will be available in early Spring 2012 for adoption in Fall 2012; the other three books will follow in Fall 2012.

OpenStax College free textbooks are developed and peer-reviewed by educators to ensure they are readable, accurate, and meet the scope and sequence requirements for college courses.  Through our partnerships with companies and foundations committed to reducing costs for students, OpenStax College is working to improve access to higher education for all.  OpenStax College is an initiative of Rice University and is made possible through the generous support of the Hewlett, Gates, 20 Million Minds, and Maxfield Foundations.

For more information, see the OpenStax College website and press release.

OpenStax College is proudly powered by Connexions.

The Fourth Annual Connexions Conference will be held on 15 February 2012 at Rice University.  Each year the Connexions Conference brings together more than 100 education thought leaders from around the world.  This year’s conference promises to be especially exciting, as we launch large scale initiatives on open textbooks and open education technology.

Please visit conference.cnx.org to register + find out more about the conference and software and content sprints on 16, 17 February 2012.  (Register before 17 January 2012 and take advantage of the early bird discount.)

“The problem with a mini-deal is we have a maxi-problem,” said John Cornyn, Senator from Texas, recently.  Indeed, minimax analysis is all over the news of late.  Our response consists of two new papers.  The first shows that the popular nonlocal means (NLM) image denoising algorithm is sub-optimal for images with sharp edges from the so-called Horizon class.  The second develops an enhanced anisotropic nonlocal means (ANLM) algorithm that is near-optimal for Horizon class images.

A. Maleki, M. Narayan, and R. G. Baraniuk, “Suboptimality of Nonlocal Means for Images with Sharp Edges,” preprint, 2011.

Abstract:  We conduct an asymptotic risk analysis of the nonlocal means image denoising
algorithm for the Horizon class of images that are piecewise constant with a sharp edge discontinuity.  We prove that the mean square risk of an optimally tuned nonlocal means algorithm decays according to n^(-1)log^(1/2)(n), for an n-pixel image.  This decay rate is an improvement over some of the predecessors of this algorithm, including the linear convolution filter, median filter, and the SUSAN filter, each of which provides a rate of only n^(-2/3).  It is also within a logarithmic factor from optimally tuned wavelet
thresholding.  However, it is still substantially lower than the the optimal minimax rate of n^(-4/3).

A. Maleki, M. Narayan, and R. G. Baraniuk, “Anisotropic Nonlocal Means Denoising,” preprint, 2011.

Abstract:  It has recently been proved that the popular nonlocal means (NLM) denoising algorithm does not optimally denoise images with sharp edges.  Its weakness lies in the isotropic nature of the neighborhoods it uses in order to set its smoothing weights.  In response, in this paper we introduce several theoretical and practical anisotropic nonlocal means (ANLM) algorithms and prove that they are near minimax optimal for edge-dominated images from the Horizon class.  On real-world test images, an ANLM algorithm that adapts to the underlying image gradients outperforms NLM by a significant margin, up to 2dB in mean square error.

Andrew E. Waters, Aswin C. Sankaranarayanan, Richard G. Baraniuk, “SpaRCS: Recovering Low-Rank and Sparse Matrices from Compressive Measurements,” in Advances in Neural Information Processing Systems (NIPS), Granada, Spain, December 2011.

Abstract:  We consider the problem of recovering a matrix M that is the sum of a low-rank matrix L and a sparse matrix S from a small set of linear measurements of the form Y = A(M) = A(L+S).  This model subsumes three important classes of signal recovery problems:  compressive sensing, affine rank minimization, and robust principal component analysis.  We propose a natural optimization problem for signal recovery under this model and develop a new greedy recovery algorithm called SpaRCS.  SpaRCS inherits a number of desirable properties from the state-of-the-art CoSaMP and ADMiRA algorithms, including exponential convergence and efficient implementation.  Simulation results with video compressive sensing, hyperspectral imaging, and robust matrix completion data sets demonstrate both the accuracy and efficacy of the algorithm.

An example from the paper illustrating the efficacy of SpaRCS for video compressive sensing (CS).  (a) Several 128×128 pixel image frames from a 201 frame ground truth video.  These were sensed by a simulated single-pixel CS camera that operates independently on each image frame.  (b) The recovered low-rank component L captures the static background.  (c) The recovered sparse component S captures the people walking in the foreground. The total recovery SNR is 31.2 dB at a measurement rate of 15% of the total number of video voxels.

J. N. Laska and R. G. Baraniuk, “Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing,” preprint, 2011.

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 200×200 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