Nuit Blanche

It's quite simply, the stuff of Life...

2012-01-28T12:05:00.000-06:00

As I was watching the excellent video presentation of Path coding penalties for directed acyclic graphs by Julien Mairal who uses SPAMS for metabolic network detection (: SPAMS (SPArse Modeling Software) by Julien Mairal, Francis Bach, Jean Ponce,Guillermo Sapiro.is listed on the Matrix Factorization Jungle Page). I was reminded of the fact that, at some point, there needs to be a serious discussion on the connection between regularization techniques, structured sparsity and their roots in the physical world. I wrote two entries on the subject a month ago:

This is not the first time that metabolic networks have been mentioned here:( Instances of Null Spaces: Can Compressive Sensing Help Study Non Steady State Metabolic Networks ? ). But what really triggered this entry is a salient question by an audience member at the very end of the talk. At that point.Julien has to explain if somehow his structured sparsity would remove loops. It turns out that, in metabolic systems like the ones Julien explores, loops are quite simply the stuff of Life. Take for instance the Krebs cycle:

In other words, choosing an ad-hoc regularization will impact your discovery process. TV regularization may be fine for getting good looking pictures and so we are OK with the fact that it is ad-hoc, but if we are to venture outside of that "image processing" garden of Lena and her sisters, we need to think hard about the connection between regularization and its connection to physical world. As mentioned in the entries listed above, Adrian Bejan's work seems to be a worthwhile, if empirical, path in that direction. I am sure there are others, but that discussion needs to occur.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Learning Sparse Representations of High Dimensional Data on Large Scale Dictionaries

2012-01-27T12:01:00.000-06:00

Using random projections to control the information flow from layer to layer in dictionary learning, this is what Zhen James Xiang seems to be saying in his NIPS11 presentation on Learning Sparse Representations of High Dimensional Data on Large Scale Dictionaries. The attendant MATLAB Toolbox is here and is featured in the Matrix Factorization Jungle Page. The paper is: Learning sparse representations of high dimensional data on large scale dictionaries by Zhen James Xiang , Hao Xu, Peter Ramadge. The abstract reads:

Learning sparse representations on data adaptive dictionaries is a state-of-the-art method for modeling data. But when the dictionary is large and the data dimension is high, it is a computationally challenging problem. We explore three aspects of the problem. First, we derive new, greatly improved screening tests that quickly identify codewords that are guaranteed to have zero weights. Second, we study the properties of random projections in the context of learning sparse representations. Finally, we develop a hierarchical framework that uses incremental random projections and screening to learn, in small stages, a hierarchically structured dictionary for sparse representations. Empirical results show that our framework can learn informative hierarchical sparse representations more efﬁciently.

And some Supplemental material.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

GRASTA: Grassmannian Robust Adaptive Subspace Tracking Algorithm Implementation

2012-01-27T03:39:00.000-06:00

Laura Balzano and Jun He let me know that they have posted information and code for the GRASTA online robust-PCA algorithm which can be applied to both Matrix Completion and Robust PCA. It is also now listed in the Matrix Factorization Jungle Page. The webpage starts with:

GRASTA

This webpage introduces an efficient online algorithm GRASTA ( Grassmannian Robust Adaptive Subspace Tracking Algorithm ) for low rank subspace tracking, which is robust to both highly incomplete information and sparse corruption by outliers.

Our work is a robust counterpart of GROUSE which is very efficient for low rank subspace tracking from highly incomplete information. Though the two algorithms share the same characteristic - stochastic gradient descent on Grassmannian - GRASTA incorporates the augmented Lagrangian of l1-norm loss function into the Grassmannian optimization framework to alleviate the corruption by outliers in the subspace update at each gradient step.

As an online algorithm, GRASTA can estimate and track non-stationary subspaces when the streaming data vectors are corrupted with outliers. We apply GRASTA to the problems of robust matrix completion and real-time separation of background from foreground in video. In this second application, we show that GRASTA performs high-quality separation of moving objects from background at exceptional speeds: In one popular benchmark video example, GRASTA achieves a rate of 57 frames per second, even when run in MATLAB on a personal laptop.

We have posted our GRASTA paper at arXiv. For more detailed information please refer to our paper. If you have some questions on our work, please email us or feel free to visit our websites: Jun He and Laura Balzano.

Thanks Laura and Jun...

Random Feedbacks

2012-01-26T04:31:00.003-06:00

Phil Schniter sent me the following yesterday following a link to the recent arxiv preprint: Approximate Message Passing under Finite Alphabet Constraints by Andreas Muller, Dino Sejdinovic, Robert Piechocki

"..hi igor,

Regarding the paper "Approximate Message Passing under Finite Alphabet Constraints", it's a great idea to exploit such prior info when available. for fairness, your readers may be be interested to hear that finite-alphabet priors have been part of the GAMPmatlab package (http://gampmatlab.wikia.com/wiki/Generalized_Approximate_Message_Passing) since its inception. moreover, such priors have been used with GAMP to do joint decoding and channel estimation in our work http://www2.ece.ohio-state.edu/~schniter/pdf/jstsp11_ofdm.pdf.

cheers,

phil..."

Thanks Phil. You all probably remembered when Phil schooled me in alphabet issues ( A Small Q&A with Phil Schniter on TurboGAMP. )

I came across this very nice example in the Python based Scikits Learn package of a Compressive sensing: tomography reconstruction with L1 prior (Lasso). Let us recall that another solver written in Python includes the ASPICS toolbox.

Talking about Phil and ASPICS reminded that I drew a graph of the recent events that occurred in 2011 in compressive sensing, both Phil and the folks behind ASPICS (Florent Krzakala, Marc Mézard, François Sausset, Yifan Sun, Lenka Zdeborová) played a no small part in these improvements. I don't know if it came out right but here it is:

Anna Gilbert has a new entries on her two recent lectures on compressive sensing.

Finally, on Quora I asked: In the Qualcomm X Prize, what should the 15 diseases be using an ultrasound based Tricorder?

Compressive Sensing This Week

2012-01-25T03:58:00.002-06:00

Here are some of the papers that showed up on my radar screen, enjoy!

First there is this presentation of Henry Pfister entitled Achieving Universality in Practice via Spatially-Coupled LDPC Codes

Next we have a few open papers:

Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit by Alexandra Carpentier, Rémi Munos. The abstract reads:

We consider a linear stochastic bandit problem where the dimension $K$ of the unknown parameter $\theta$ is larger than the sampling budget $n$. In such cases, it is in general impossible to derive sub-linear regret bounds since usual linear bandit algorithms have a regret in $O(K\sqrt{n})$. In this paper we assume that $\theta$ is $S-$sparse, i.e.~has at most $S-$non-zero components, and that the space of arms is the unit ball for the $||.||_2$ norm. We combine ideas from Compressed Sensing and Bandit Theory and derive algorithms with regret bounds in $O(S\sqrt{n})$.

ADAPTIVE COMPRESSED SENSING FOR VIDEO ACQUISITION by Hassan Mansour and Ozgur Yılmaz. The abstract reads:

In this paper, we propose an adaptive compressed sensing scheme that utilizes a support estimate to focus the measurements on the large valued coefﬁcients of a compressible signal. We embed a “sparse-ﬁltering” stage into the measurement matrix by weighting down the contribution of signal coefﬁcients that are outside the support estimate. We present an application which can beneﬁt from the proposed sampling scheme, namely, video compressive acquisition. We demonstrate that our proposed adaptive CS scheme results in a signiﬁcant improvement in reconstruction quality compared with standard CS as well as adaptive recovery using weighted `1 minimization.

Blind Spectrum Detector for Cognitive Radio using Compressed Sensing by Ziad Khalaf , Amor Nafkha , Jacques Palicot. The abstract reads:

Based on the sparse property of the cyclic autocorrelation in the cyclic frequencies domain, this paper proposes a new blind spectrum sensing method which uses the compressed sensing technique in order to detect free bands in the radio spectrum. This new sensing method that presents a relative low complexity has the particularity to perform blind and robust detection with only few samples (short observation time) and without any knowledge about the cyclic frequency of the signal, in contrary to cyclostationary detection methods that are not robust when the sample size is small and might need some information about the signal in order to detect. ROC curves obtained by simulation show the superiority of the new proposed technique over cyclostationary detection under the same conditions, particularly the same observation time.

Approximate Message Passing under Finite Alphabet Constraints by Andreas Muller, Dino Sejdinovic, Robert PiechockiThe abstract reads:

In this paper we consider Basis Pursuit De-Noising (BPDN) problems in which the sparse original signal is drawn from a finite alphabet. To solve this problem we propose an iterative message passing algorithm, which capitalises not only on the sparsity but by means of a prior distribution also on the discrete nature of the original signal. In our numerical experiments we test this algorithm in combination with a Rademacher measurement matrix and a measurement matrix derived from the random demodulator, which enables compressive sampling of analogue signals. Our results show in both cases significant performance gains over a linear programming based approach to the considered BPDN problem. We also compare the proposed algorithm to a similar message passing based algorithm without prior knowledge and observe an even larger performance improvement.

Compressive Acquisition of Dynamic Scenes by Aswin C Sankaranarayanan, Pavan K Turaga, Rama Chellappa, Richard G Baraniuk. The abstract reads:

Compressive sensing (CS) is a new approach for the acquisition and recovery of sparse signals and images that enables sampling rates significantly below the classical Nyquist rate. Despite significant progress in the theory and methods of CS, little headway has been made in compressive video acquisition and recovery. Video CS is complicated by the ephemeral nature of dynamic events, which makes direct extensions of standard CS imaging architectures and signal models difficult. In this paper, we develop a new framework for video CS for dynamic textured scenes that models the evolution of the scene as a linear dynamical system (LDS). This reduces the video recovery problem to first estimating the model parameters of the LDS from compressive measurements, and then reconstructing the image frames. We exploit the low-dimensional dynamic parameters (the state sequence) and high-dimensional static parameters (the observation matrix) of the LDS to devise a novel compressive measurement strategy that measures only the dynamic part of the scene at each instant and accumulates measurements over time to estimate the static parameters. This enables us to lower the compressive measurement rate considerably. We validate our approach with a range of experiments involving both video recovery, sensing hyper-spectral data, and classification of dynamic scenes from compressive data. Together, these applications demonstrate the effectiveness of the approach.

On Detection-Directed Estimation Approach On Detection-Directed Estimation Approach for Noisy Compressive Sensing by Jaewook Kang, Heung-No Lee, Kiseon Kim. The abstract reads:

In this paper, we investigate a Bayesian sparse reconstruction algorithm called compressive sensing via Bayesian support detection (CS-BSD). This algorithm is quite robust against measurement noise and achieves the performance of a minimum mean square error (MMSE) estimator that has support knowledge beyond a certain SNR threshold. The key idea behind CS-BSD is that reconstruction takes a detection-directed estimation structure consisting of two parts: support detection and signal value estimation. Belief propagation (BP) and a Bayesian hypothesis test perform support detection, and an MMSE estimator finds the signal values belonging to the support set. CS-BSD converges faster than other BP-based algorithms, and it can be converted to a parallel architecture to become much faster. Numerical results are provided to verify the superiority of CS-BSD compared to recent algorithms.

On the Lagrangian Biduality of Sparsity Minimization Problems by Dheeraj Singaraju, Ehsan Elhamifar, Roberto Tron, Allen Y. Yang, S. Shankar Sastry. The abstract reads:

Recent results in Compressive Sensing have shown that, under certain conditions, the solution to an underdetermined system of linear equations with sparsity-based regularization can be accurately recovered by solving convex relaxations of the original problem. In this work, we present a novel primal-dual analysis on a class of sparsity minimization problems. We show that the Lagrangian bidual (i.e., the Lagrangian dual of the Lagrangian dual) of the sparsity minimization problems can be used to derive interesting convex relaxations: the bidual of the $\ell_0$-minimization problem is the $\ell_1$-minimization problem; and the bidual of the $\ell_{0,1}$-minimization problem for enforcing group sparsity on structured data is the $\ell_{1,\infty}$-minimization problem. The analysis provides a means to compute per-instance non-trivial lower bounds on the (group) sparsity of the desired solutions. In a real-world application, the bidual relaxation improves the performance of a sparsity-based classification framework applied to robust face recognition.

A General Framework of Dual Certificate Analysis for Structured Sparse Recovery Problems by Cun-Hui Zhang, Tong Zhang. The abstract reads:

This paper develops a general theoretical framework to analyze structured sparse recovery problems using the notation of dual certificate. Although certain aspects of the dual certificate idea have already been used in some previous work, due to the lack of a general and coherent theory, the analysis has so far only been carried out in limited scopes for specific problems. In this context the current paper makes two contributions. First, we introduce a general definition of dual certificate, which we then use to develop a unified theory of sparse recovery analysis for convex programming. Second, we present a class of structured sparsity regularization called structured Lasso for which calculations can be readily performed under our theoretical framework. This new theory includes many seemingly loosely related previous work as special cases; it also implies new results that improve existing ones even for standard formulations such as L1 regularization.

Compressed Beamforming Applied to B-Mode Ultrasound Imaging by Noam Wagner, Yonina C. Eldar, Arie Feuer, Zvi Friedman.The abstract reads:

Emerging sonography techniques often imply increasing in the number of transducer elements involved in the imaging process. Consequently, larger amounts of data must be acquired and processed by the beamformer. The significant growth in the amounts of data effects both machinery size and power consumption. Within the classical sampling framework, state of the art systems reduce processing rates by exploiting the bandpass bandwidth of the detected signals. It has been recently shown, that a much more significant sample-rate reduction may be obtained, by treating ultrasound signals within the Finite Rate of Innovation framework. These ideas follow the spirit of Xampling, which combines classic methods from sampling theory with recent developments in Compressed Sensing. Applying such low-rate sampling schemes to individual transducer elements, which detect energy reflected from biological tissues, is limited by the noisy nature of the signals. This often results in erroneous parameter extraction, bringing forward the need to enhance the SNR of the low-rate samples. In our work, we manage to achieve such SNR enhancement, by beamforming the sub-Nyquist samples obtained from multiple elements. We refer to this process as "compressed beamforming". Applying it to cardiac ultrasound data, we successfully image macroscopic perturbations, while achieving a nearly eight-fold reduction in sample-rate, compared to standard techniques.

Reconstruction of HARDI using Compressed Sensing and its Application to Contrast HARDI by Sudipto Dolui, Ivan C. Salgado Patarroyo, Oleg V. Michailovich., Yogesh Rathi. The abstract reads:

High angular resolution diffusion imaging (HARDI) is known to excel in delineating multiple diffusion ﬂows through a given location within the white matter of the brain. Unfortunately, many current methods of implementation of HARDI require collecting a relatively large number of diffusion-encoded images, which is in turn translated in prohibitively long acquisition times. As a possible solution to this problem, one can undersample HARDI data by using fewer diffusion-encoding gradients than it is prescribed by the classical sampling theory, while exploiting the tools of compressed sensing (CS). Accordingly, the goal of the present paper is twofold. First, the paper presents a novel CS-based framework for the reconstruction of HARDI data using a reduced set of diffusion-encoding gradients. As opposed to similar studies reported in the literature, the proposed method has been optimized for the Rician statistics of measurement noises, which are known to be prevalent in HARDI, and in fact, in MRI in general. Second, we introduce the concept of rotational invariant Fourier signatures (RIFS), and show how they can be used to generate a composite HARDI contrast, which we refer to as colour-HARDI (cHARDI). Finally, via a series of experiments with both simulated and in vivo MRI data, we demonstrate that the quality and informativeness of the proposed contrast deteriorates little, when used in conjunction with the proposed CS-based reconstruction framework. Thus the present work proposes a way to improve the time efﬁciency of HARDI, and shows its application to the computation of a new HARDI-based contrast which has a potential to improve the clinical value of this important imaging modality.

Sparse Binary Matrices of LDPC codes for Compressed Sensing by Weizhi Lu , Kidiyo Kpalma , Joseph Ronsin. The abstract reads:

Compressed sensing shows that one undetermined measurement matrix can losslessly compress sparse signals if this matrix satisfies Restricted Isometry Property (RIP). However, in practice there are still no explicit approaches to construct such matrices. Gaussian matrices and Fourier matrices are first proved satisfying RIP with high probabilities. Recently, sparse random binary matrices with lower computation load also expose comparable performance with Gaussian matrices. But they are all constructed randomly, and unstable in orthogonality. In this paper, inspired by these observations, we propose to construct structured sparse binary matrices which are stable in orthogonality. The solution lies in the algorithms that construct parity-check matrices of low-density parity-check (LDPC) codes. Experiments verify that proposed matrices significantly outperform aforementioned three types of matrices. And significantly, for this type of matrices with a given size, the optimal matrix for compressed sensing can be approximated and constructed according to some rules.

Parallel imaging technique using localized gradients (PatLoc) reconstruction using compressed sensing (CS)
by F-H. Lin, P. Vesanen, T. Witzel, R. Ilmoniemi, and J. Hennig. The abstract reads:

Parallel acquisition with localized gradient (PatLoc) is a new approach to further increase degrees of freedom in spatial encoding by using a combination of surface gradient coils [1]. Due to non-bijective encoding, PatLoc requires a radio-frequency coil array to uniquely localize the magnetization using the parallel MRI approach [1]. Preliminary results of PatLoc image reconstructions focused on the accelerated acquisitions not exceeding the number of RF coil in the array [2,3,4,5]. Recently, based on the assumption of image sparsity, compressed sensing (CS) has been proposed to achieve MRI acceleration using random sampling k-space and reconstructing vastly reduced data using a nonlinear algorithm [6]. In this study, we investigate the feasibility of reconstructing highly accelerated PatLoc images using CS. Specifically, we hypothesize that PatLoc can provide better reconstructed images compared to traditional orthogonal linear gradient systems because of higher degree of freedom in spatial encoding.

On the Beneﬁt of using Tight Frames for Robust Data Transmission and Compressive Data Gathering in Wireless Sensor Networks by Wei Chen, Miguel R. D. Rodrigues and Ian J. Wassell. The abstract reads:

Compressive sensing (CS), a new sampling paradigm, has recently found several applications in wireless sensor networks (WSNs). In this paper, we investigate the design of novel sensing matrices which lead to good expected-case performance - a typical performance indicator in practice - rather than the conventional worst-case performance that is usually employed when assessing CS applications. In particular, we show that tight frames perform much better than the common CS Gaussian matrices in terms of the reconstruction average mean squared error (MSE). We also showcase the beneﬁts of tight frames in two WSN applications, which involve: i) robustness to data sample losses; and ii) reduction of the communication cost.

Spatially sparse source cluster modeling by compressive neuromagnetic tomography by Wei-Tang Chang, Aapo Nummenmaa, Jen-Chuen Hsieh, Fa-Hsuan Lin. The abstract reads:

Magnetoencephalography enables non-invasive detection of weak cerebral magnetic ﬁelds by utilizing superconducting quantum interference devices (SQUIDs). Solving the MEG inverse problem requires reconstructing the locations and orientations of the underlying neuronal current sources based on the extracranial measurements. Most inverse problem solvers explicitly favor either spatially more focal or diffuse current source patterns. Naturally, in a situation where both focal and spatially extended sources are present, such reconstruction methods may yield inaccurate estimates. To address this problem, we propose a novel ComprEssive Neuromagnetic Tomography (CENT) method based on the assumption that the current sources are compressible. The compressibility is quantiﬁed by the joint sparsity of the source representation in the standard source space and in a transformed domain. The purpose of the transformation sparsity constraint is to incorporate local spatial structure adaptively by exploiting the natural redundancy of the source conﬁgurations in the transform domain. By combining these complementary constraints of standard and transformed domain sparsity we obtain source estimates, which are not only locally smooth and regular but also form globally separable clusters. In this work, we use the ℓ1-norm as a measure of sparsity and convex optimization to yield compressive estimates in a computationally tractable manner. We study the Laplacian matrix (CENTL) and spherical wavelets (CENTW) as alternatives for the transformation in the compression constraint. In addition to the two prior constraints on the sources, we control the discrepancy between the modeled and measured data by restricting the power of residual error below a speciﬁed value. The results show that both CENTL and CENTW are capable of producing robust spatially regular source estimates with high computational efﬁciency. For simulated sources of focal, diffuse, or combined types, the CENT method shows better accuracy on estimating the source locations and spatial extents than the minimumℓ1-norm or minimum ℓ2-norm constrained inverse solutions. Different transformations yield different beneﬁts: By utilizing CENT with the Laplacian matrix it is possible to suppress physiologically atypical activations extending across two opposite banks of a deep sulcus. With the spherical wavelet transform CENT can improve the detection of two nearby yet not directly connected sources. As demonstrated by simulations, CENT is capable of reﬂecting the spatial extent for both focal and spatially extended current sources. The analysis of in vivo MEG data by CENT produces less physiologically inconsistent “clutter” current sources in somatosensory and auditory MEG measurements. Overall, the CENT method is demonstrated to be a promising tool for adaptive modeling of distributed neuronal currents associated with cognitive tasks.

The following papers are behind a paywall:

Image Credit: NASA/JPL/Space Science Institute, W00071921.jpg was taken on January 22, 2012 and received on Earth January 24, 2012. The camera was pointing toward SATURN at approximately 2,479,787 kilometers away, and the image was taken using the MT2 and CL2 filters.

Around the blogs in 80 hours, prizes and fame.

2012-01-24T03:18:00.001-06:00

On metaoptmize, there is a question about compressive sensing recovery. Bob has some interesting 'misses' findings on audio classification with music samples, watch out though that blog entry could become addictive! Dirk talks about Sparse recovery of multidimensional signal with Kronecker products. Danny has updated his post on Hyperspectral imaging using GraphLab. Randy features a press release by a company that clearly thinks about the X-Prize tricorder and finally Greg talks about this week's MIT course where the students build a DIY Phased Array Radar using pegboard and wi-fi antennas. He has more in this entry.

Some folks received some prizes directly or indirectly thanks to their contribution to compressive sensing:

The Crafoord prize was handed out to some people connected to compressive sensing (Terry Tao)

Today the Royal Swedish Academy of Sciences announced the four winners of the 2012 Crafoord Prize, an annual award that rotates between the disciplines of astronomy, mathematics, geosciences, biosciences, and arthritis research. This year's honorees came from mathematics and astronomy, fields last recognized in 2008.
The two awardees in mathematics were Jean Bourgain, a Belgian mathematician now working at the Institute for Advanced Study (IAS) in Princeton, New Jersey, and Terence Tao, an Australian-American mathematician at the University of California, Los Angeles (UCLA). Both Bourgain and Tao previously won the Fields Medal, often considered the equivalent of the Nobel Prize in mathematics (Bourgain in 1994 and Tao in 2006).

Mario Figueiredo let us know that he received with his co-authors the IEEE SPS Best Paper Award. on the SpaRSA algorithm
Clara Fannjiang of Davis High School is a semifinalist in the Intel Science Talent Search. (theme of her work : Better images, fewer samplesOptimizing array configuration for compressed sensing in radio interferometry)

And finally Nuit Blanche did not get no prizes but was mentioned in the comment section of an op-ed of the New York Times, yes and soon fame and fortune, world domination at last, muuuuaaaaaaaahhhhhhhh.

The Bregman Iterative Procedure

2012-01-23T00:01:00.000-06:00

Do not confuse this with the linearized Bregman method!

so says the Bregman Iterative Procedure site: where is featured this paper: Error Forgetting of Bregman Iteration. by Wotao Yin and Stanley Osher. The abstract reads:

This short article analyzes an interesting property of the Bregman iterative procedure, which is

equivalent to the augmented Lagrangian method, for minimizing a convex piece-wise linear function J(x) subject to linear constraints Ax = b. The procedure obtains its solution by solving a sequence of unconstrained subproblems of minimizing J(x)+ 12kAx−bkk22, where bk is iteratively updated. In practice, the subproblems can be solved at relatively low accuracy. Let w k denote the numerical error at iteration k. If all w k are sufficiently small so that Bregman iteration identifies the optimal face, then on the optimal face, Bregman iteration enjoys an interesting error-forgetting property: the distance between the current point ˉx k and the optimal solution set X is bounded by kwk+1− wkk, independent of the numerical errors at previous iterations. This property partially explains why the Bregman iterative procedure works well for sparse optimization and, in particular, l1-minimization. The error-forgetting property is unique to piece-wise linear functions (i.e., polyhedral functions) J(x), and the results of this article appears to new to the literature of the augmented Lagrangian method.

The attendant code for this procedure can be found here.

sFFT: Sparse Fast Fourier Transform

2012-01-22T16:59:00.000-06:00

Remember the new FFT algorithm out of MIT that uses the sparsity of the signal to perform a Faster FFT ? Well, the authors (Dina Katabi, Piotr Indyk, Haitham Hassanieh, Eric Price), just set up a website that will eventually host an implementation of it. ( Piotr tells me it should be up after the news storm has settled down). The KIHP sFFT page currently starts with:

IntroductionWe consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coefficients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal pro- cessing, notably Gaussian and Dolph-Chebyshev filters. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice.

Algorithm

Algorithm

Complexity

Sparsity Range

sFFT 1.0 (Non-Iterative Alghorithm) ::

sFFT 2.0 (sFFT 1.0 + Heuristic) ::

sFFT 3.0 (Exact k Sparse Algorithm) ::

sFFT 4.0 (General k Sparse Algorithm) ::

Lower Bound ::

The figure of deep interest is here I think with a comparison with the Fastest Fourier Transform in the West . (FFTW)

The paper presented at SODA is Simple and Practical Algorithm for Sparse Fourier Transform by Haitham Hassanieh , Piotr Indyk , Dina Katabi, and Eric Price. The abstract reads:

. We consider the sparse Fourier transform problem: given a complex vector x of length n, and a parameter k, estimate the k largest (in magnitude) coeﬃcients of the Fourier transform of x. The problem is of key interest in several areas, including signal processing, audio/image/video compression, and learning theory. We propose a new algorithm for this problem. The algorithm leverages techniques from digital signal processing, notably Gaussian and Dolph-Chebyshev ﬁlters. Unlike the typical approach to this problem, our algorithm is not iterative. That is, instead of estimating “large” coeﬃcients, subtracting them and recursing on the reminder, it identiﬁes and estimates the k largest coeﬃcients in “one shot”, in a manner akin to sketching/streaming algorithms. The resulting algorithm is structurally simpler than its predecessors. As a consequence, we are able to extend considerably the range of sparsity, k, for which the algorithm is faster than FFT, both in theory and practice.

Video: Stephen Wright "Regularized Optimization".

2012-01-22T16:30:00.000-06:00

Also at SPARS11, here is Stephen Wright's plenary lecture entitled "Regularized Optimization".

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing SPARS11, video taping these lectures and putting them on the site.

Video: Martin Vetterli "Sampling in the Age of Sparsity"

2012-01-22T15:30:00.000-06:00

Also at SPARS11, here is Martin Vetterli's plenary lecture entitled Sampling in the Age of Sparsity.

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing SPARS11, video taping these lectures and putting them on the site.

Video: Joel Tropp "Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

2012-01-22T14:30:00.000-06:00

Also at SPARS11, here is Joel Tropp's plenary lecture entitled "Probabilistic Algorithms for Constructing Approximate Matrix Decompositions".

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing SPARS11, video taping these lectures and putting them on the site.

Video: Yi Ma: "Low Dimensional Structures in Images (or Data)".

2012-01-22T13:30:00.000-06:00

Also at SPARS11, here is Yi Ma's plenary lecture entitled "Low Dimensional Structures in Images (or Data)".

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing SPARS11, video taping these lectures and putting them on the site.

Video: Remi Gribonval "An Overview of Analysis vs Synthesis in Low-Dimensional Signal Models"

2012-01-22T12:30:00.000-06:00

Also at SPARS11, here is Remi Gribonval plenary lecture entitled "An Overview of Analysis vs Synthesis in Low-Dimensional Signal Models". The work echoes the presentation made by Miki Elad at MIA2012.

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing SPARS11, video taping these lectures and putting them on the site.

Video: David Donoho "Precise Asymptotics in Compressed Sensing"

2012-01-22T11:30:00.000-06:00

Also at SPARS11, here is David Donoho plenary lecture entitled "Precise Asymptotics in Compressed Sensing"

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing SPARS11, video taping these lectures and putting them on the site.

Video: David Brady's "Coding for Multiplex Optical Imagers" lecture

2012-01-21T16:08:00.002-06:00

SPARS11 took place 7 months ago but I still enjoy the plenary lectures on video. Today, I re-watched David Brady's presentation on Coding for Multiplex Optical Imagers. It's just awesome. I tried to put the video on Youtube but it is too long. I tried Vimeo but I have uploading issues. Oh well, at least it is in a wmv format (if anyone uploads them somewhere on a player, please let me know, I'll link to the video and your site will be duly acknowledged).

The other plenary lectures (they last about 45 minutes) are listed below:

Thanks to Coralia Cartis, Mike Davies, Jared Tanner and Bubacarr Bah for organizing the meeting, video taping these lectures and putting them on the site.

Robust Denoise This!

2012-01-20T10:19:00.000-06:00

Forget Lena

Julien just mentioned to me some extraordinary shots taken yesterday at the Fukushima plant that could be useful for some of you over the week-end (if you are interested): Namely, clean up video footages from reactor 2 of the Fukushima Daiichi plant taken yesterday.

In the following handout by TEPCO entitled: Trial examination at Fukushima Daiichi Nuclear Power Station Unit 5 for inner inspection of PCV of Fukushima Daiichi Nuclear Power Unit 2, one gets an idea of the examination work that is currently undertaken at Fukushima in order to investigate the primary containment vessel of reactor 2. Less than a year later, we are getting videos to watch, wow, this is simply amazing in terms of transparency. Of interest to the image processing and denoising folks, is the amount of noise from all kinds on these photos and videos. Specifically, radiation hits the FPA of the camera pretty hard. I wonder how any of the current Robust PCA (or similar work) that Nuit Blanche often features behave in such an uncontrolled benchmark.

I am tempted to see how some denoising and other inpainting could make these videos nicer

of interest eventually, is the ability to have future vision test inside the reactor enabled by these denoising techniques.

Most information (including the original videos come from this page but they won't be up for too long, get them while you can):

"...Investigation inside of Primary Containment Vessel, Unit 2, Fukushima Daiichi NPS

The digest version

(Video on January 19, 2012)

Videos

*Video File For Download(This file will expire after 7 days.)

Inside of the Primary Containment Vessel, Unit 2 (Video1)(256MB)

(Video on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (Video2)(117MB)

(Video on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (Video3)(92.1MB)

(Video on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (Video4)(644MB)

(Video on January 19, 2012)

[Reference] Endoscope used for the insight survey of Primary Containment Vessel of Unit2 of Fukushima Daiichi Nuclear Power Station on January 19, 2012(PDF 38.7KB)

Endoscope(1)

(pictured on January 18, 2012)

Endoscope(2)

(pictured on January 18, 2012).

[Reference] Investigation inside of Primary Containment Vessel, Unit 2, Fukushima Daiichi NPS (124KB)

Inside of the Primary Containment Vessel, Unit 2 (1)

(pictured on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (2)

(pictured on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (3)

(pictured on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (4)

(pictured on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (5)

(pictured on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (6)

(pictured on January 19, 2012)

Inside of the Primary Containment Vessel, Unit 2 (7)

(pictured on January 19, 2012)

."

Thanks Julien!

Machine-Learning with Real-time & Streaming Applications

2012-01-20T05:03:00.000-06:00

Dan Starr just sent me the following:

We are organizing a meeting on the UC Berkeley campus on a topic which may be of interest to your Nuit-Blanche website and may warrant being mentioned under your "CS meetings related to compressive sensing". If interested, please feel free to add this conference or disseminate the following announcement.

Sure Dan , it looks very interesting:

FIRST CONFERENCE ANNOUNCEMENT:
From Data to Knowledge: Machine-Learning with Real-time & Streaming ApplicationsMay 7-11 2012On the Campus of the University of California, Berkeley
http://lyra.berkeley.edu/CDIConf/

* * CONFIRMED INVITED SPEAKERS * *
Olfa Nasraoui (Louisville), Petros Drineas (RPI), Muthu Muthukrishnan (Rutgers), Alex Szalay (John Hopkins), David Bader (Georgia Tech), Eamonn Keogh (UC Riverside), Joao Gama (Univ. of Porto, Portugal), Michael Franklin (UC Berkeley), Ziv Bar-Joseph (Carnegie Mellon University)

* * AIMS OF THE CONFERENCE * *
We are experiencing a revolution in the capacity to quickly collect and transport large amounts of data. Not only has this revolution changed the means by which we store and access this data, but has also caused a fundamental transformation in the methods and algorithms that we use to extract knowledge from data. In scientific fields as diverse as climatology, medical science, astrophysics, particle physics, computer vision, and computational finance, massive streaming data sets have sparked innovation in methodologies for knowledge discovery in data streams. Cutting-edge methodology for streaming data has come from a number of diverse directions, from on-line learning, randomized linear algebra and approximate methods, to distributed optimization

methodology for cloud computing, to multi-class classification problems in the presence of noisy and spurious data.

This conference will bring together researchers from applied mathematics and several diverse scientific fields to discuss the current state of the art and open research questions in streaming data and real-time machine learning. The conference will be domain driven, with talks focusing on well-defined areas of application and describing the techniques and algorithms necessary to address the current and future challenges in the field.

Sessions will be accessible to a broad audience and will have a single track format with additional rooms for breakout sessions and posters. There will be no formal conference proceedings, but conference applicants are encouraged to submit an abstract and present a talk and/or poster.

* * IMPORTANT DATES * *
Feb 29 : Initial registration ends, participants announced.May 7 - 11 : Conference.

* * SESSIONS * *
Stochastic Data Streams Muthu Muthukrishnan: (Dept. of Computer Science, Rutgers University)
Real-Time Machine Learning in Astrophysics Alex Szalay: (Dept. of Physics and Astronomy, John Hopkins University)
Real-Time Analytics with Streaming Databases Michael Franklin: (Computer Science Dept., UC Berkeley)
Classification of Sensor Network Data Streams Joao Gama: (Lab. of A.I. & Decision Support, Economics at Univ. of Porto)
Randomized and Approximation Algorithms Petros Drineas: (Computer Science Dept., Rensselaer Polytechnic Institute)
Time-Series Clustering and Classification Eamonn Keogh: (Computer Science and Engineering Dept., UC Riverside)
Time Series in the Biological and Medical Sciences Ziv Bar-Joseph: (Computer Science Dept., Carnegie Mellon University)
Streaming Graph/Network Data & Architectures David Bader: (College of Computing, Georgia Tech)
Data Mining of Data Streams Olfa Nasraoui: (Dept. of CS & Computer Engineering, Univ. of Louisville)

* * Local Organizing Committee * *
Joshua Bloom: (Dept. of Astronomy, UC Berkeley)Damian Eads: (Dept. of CS, UC Santa Cruz; Dept. of Eng, Univ. of Cambridge)Berian James: (Dept. of Astr, UC Berkeley; Dark Cosmology Centre, U Copenhagen)Peter Nugent: (Comp. Cosmology, Lawrence Berkeley National Lab.)John Rice: (Dept. of Statistics, UC Berkeley)Joseph Richards: (Dept. of Astronomy & Dept. of Statistics, UC Berkeley)Dan Starr: (Dept. of Astronomy, UC Berkeley)

* * Scientific Organizing Committee * *
Leon Bottou: (NEC Labs)Emmanuel Candes: (Stanford)Brad Efron: (Stanford)Alex Gray: (Georgia Tech)Michael Jordan: (Berkeley)John Langford: (Yahoo)Fernando Perez: (Berkeley)Ricardo Vilalta: (Houston)Larry Wasserman: (CMU)

I asked Dan, if there would be any video coverage of the event:

Our current plan is not to use the IT/AV services of UC Berkeley. The Local Organizing Committee does prefer conferences with video archives, so we may find an alternative option by May.

MIT-FFT: Please think of the marketers, they are people too !

2012-01-19T04:13:00.002-06:00

Nuit Blanche has been scooped by TechCrunch! My excuse? I was too busy asking questions at MIA 2012 ( more on that later). So let us provide some context, ever since Empirical Evaluation of a Sub-Linear Time Sparse DFT Algorithm by Mark Iwen, Anna Gilbert and Martin Strauss, I had not seen much activity on one of the cornerstone algorithm of the 20th century seen through the eyes of sparsity, a subject of central interest in compressive sensing. After talking to him, Mark eventually put an implementation of the Ann Arbor FFT (AAFFT) on Sourceforge and according to the site it got about 10,000 downloads. It is a large success in our community but it definitely is not a blockbuster outside of it. The idea is to perform an FFT on a signal known to be sparse (irrespective to where it is sparse) and be computationally more efficient than the current FFT count. A week ago, a different algorithm from MIT appeared on the interwebs. that is an improvement over the AAFFT and is the subject of the TechCrunch story. Without further due here is: Nearly Optimal Sparse Fourier Transform by Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price. The abstract reads:

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show:

* An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and

* An O(k log n log(n/k))-time algorithm for general input signals.

Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). Further, they are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = n^{\Omega(1)} . We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least \Omega(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.

Folks, you need a name for this algorithm, I know you did the hard work, but please think of the marketers, they are people too! Since we already have the Fastest Fourier Transform in the West. (FFTW), I wonder if FFTE, Faster Fourier Transform in the East, would work since MIT is on the East coast...you know the usual East coast - West coast thingy ... oh well...

Call me a snob but what's interesting to me is that while this new algorithm is certainly a game changer, I am much more interested in this paper who Piotr Indyk also co-wrote which in my mind is certainly more of a 21st century problem: Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality by Sariel Har-Peled, Piotr Indyk, Rajeev Motwani. The abstract reads:

We present two algorithms for the approximate nearest neighbor problem in high dimensional spaces. For data sets of size n living in IRd , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree.

Credit Photo: NASA, Mars from Opportunity's Camera, Sol 2820

Analysis Dictionary Learning: A New Matrix Factorization ?

2012-01-17T00:01:00.000-06:00

I eventually was able to watch Miki Elad's presentation at MIA2012. While that presentation is not on his website yet, the closest I could find is: K-SVD Dictionary-Learning for Analysis Sparse Models. I had read these papers before on analysis versus synthesis and while I am still not quite clear on what is being really said (it needs to sink in first), there is I think a very interesting matrix decomposition I had not seen before:

Namely, \Omega and A are unknowns, X is known and A is made of sparse vector columns. While talking to Miki, we were wondering if this type of matrix decomposition existed or was needed in other fields of investigation (besides analysis dictionary learning for sparse models) ? Recall that the current and now mainstream dictionary learning solvers (featured in the Matrix Factorization Jungle Page) solve the following problem:

(Synthesis) Dictionary Learning: A = DX with unknown D and X, solve for sparse X

which is to be contrasted with the new decomposition:

(Analysis) Dictionary Learning A = \Omega X with unknown \Omega and A, solve for sparse A

Of the results that surprised me, the first one was pretty telling:

In short, the operator \Omega found by this dictionary learning decomposition seems to find back a TV like operator! (The Xs were made of patches).

The Nuit Blanche Mailbag

2012-01-16T00:01:00.000-06:00

MIA2012 starts today. The Call for papers: Advances in signal and image processing for physico-chemical analysis has been extended. Following up on the X-Prize Tricorder Challenge, I already have gotten a person interested. Also Phil Schniter sent me this:

Dear Igor,

I'm writing to let you know about two faculty positions in _Machine Learning_ that we recently announced at the Ohio State University. Both faculty will be jointly appointed across the departments of ECE and Biomedical Informatics (BMI). We seek candidates who will make solid theoretical contributions, and who are also excited by the real-world datasets that BMI has to offer.

More details about these positions can be found at: https://ece.osu.edu/about/employment

Perhaps you can mention this on your blog.

Thanks and best regards,

Phil

Thanks Phil for the heads-up. Dick Gordon also mentioned one of his paper in Biotechnology Focus back in 2000:

Dear Igor,

Wrote:

Blyden, E.R. & R. Gordon (2000). Genomics, pharmacology and 3D imaging: self-knowledge in the post-genomic era. Biotechnology Focus 3(6), 14, 16.

a while ago. Must be 15 diseases diagnosable via ultrasound, so that’s where I’d start.

Fifteen diseases detected through ultrasound ?! I did not realize they was even one. Thanks Dick. Finally, Jim Fowler sent the following:

Hi Igor,

I would like to let you know of a journal article that we will have appearing soon in Foundations and Trends in Signal Processing. The details are:

J. E. Fowler, S. Mun, and E. W. Tramel, “Block-Based Compressed Sensing of Images and Video,” Foundations and Trends in Signal Processing, to appear.
Abstract:

A number of techniques for the compressed sensing of imagery are surveyed. Various imaging media are considered, including still images, motion video, as well as multiview image sets and multiview video. A particular emphasis is placed on block-based compressed sensing due to its advantages in terms of both lightweight reconstruction complexity as well as a reduced memory burden for the random-projection measurement operator. For multiple-image scenarios, including video and multiview imagery, motion and disparity compensation is employed to exploit frame-to-frame redundancies due to object motion and parallax, resulting in residual frames which are more compressible and thus more easily reconstructed from compressed-sensing measurements. Extensive experimental comparisons evaluate various prominent reconstruction algorithms for still-image, motion-video, and multiview scenarios in terms of both reconstruction quality as well as computational complexity.
PDF at: http://www.ece.msstate.edu/~fowler/Publications/FMT2012.html
Best Regards,
-Jim

Thanks Jim.

One of you asked for permission to make this blog more accessible in the Middle Empire, it is a great initiative.For those of you who want to catch, you may want to download The Nuit Blanche Chronicles featuring a pdf of all the entries of most of 2011.

Finally, in the Matrix Factorization Jungle Group on LinkedIn, Danny Bickson asked the following about a GraphLab workshop:

GraphLab workshop?

Hi all,

We are thinking about arranging a graphlab workshop in the bay area around April. We thought about having demos and tutorials about graphlab v2 with some contributed talks from industry about future challenges in large scale machine learning. A preliminary list of companies who already confirmed their participation: Intel, Cloudera, WallMart Labs, Technicolor Labs, LinkedIn, Pandora Internet Radio, Oracle Labs and multiple startups. If you are interested in participating and or giving a talk please contact me.

We are also checking the possibility of planning a similar workshop at the east coast. Here we are less sure about the demand. Please contact me if you are interested!

Thanks a lot!

As a reminder, there are currently 154 members in that group and 1253 members in the compressive sensing group.

Image Credit: NASA/JPL/Space Science Institute
Full-Res: W00071706.jpg
W00071706.jpg was taken on January 13, 2012 and received on Earth January 15, 2012. The camera was pointing toward SATURN at approximately 2,801,959 kilometers away, and the image was taken using the CB2 and CL2 filters.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Another clue Journals are in the Branding Business

2012-01-14T16:00:00.000-06:00

Yaroslav pointed this entry on Christian Robert's blog. The astute reader may recall a similar point in "You think peer review as currently implemented suck ? Wait till it is going to be the only way to publish"

Request for Expression of Interest: The Qualcomm Tricorder X Prize

2012-01-13T10:39:00.000-06:00

The Qualcomm Tricorder X Prize was announced at CES this week. The goal of the competition is to build a "thing" that can be

".....capable of capturing key health metrics and diagnosing a set of 15 diseases. Metrics for health could include such elements as blood pressure, respiratory rate, and temperature. Ultimately, this tool will collect large volumes of data from ongoing measurement of health states through a combination of wireless sensors, imaging technologies, and portable, non-invasive laboratory replacements...".

I say a "thing" because it does not have to be just a portable device as one could envision by remembering the original Tricorder. The current description of the prize is pretty light on the details for the moment and the FAQ is not extraordinarily helpful....yet. For instance, right now we don't know if the 15 diseases are already known or are just up to the team to define.

Let us look at some of the response of the FAQ to get a sense of what this challenge is really about.. First of all, are we talking about Star Treck type of technology, where most of the technology either does not exist or is very low in the TRL scale ? Probably not:

"....What's new about the technology? Doesn't most of this already exist?
Yes, some of the technology exists today. However, the the teams in this competition will pull this all together in one seamless system. The resulting instrument will also push the sensing component of technology in different ways: Smaller, lighter, cheaper, faster, better. Integration of these many different components is expected to be very challenging...."

While the emphasis is on diagnostics, I note the importance of continuous monitoring

What will the Device actually do?

Diagnose diseases

Provide ongoing metrics of health (vitals)

Allow monitoring or continuous use of sensors to diagnose and measure health

Provide awareness of health state

Give confirmation that everything is ok with a consumer

Notify that something is not ok (a "check engine light")

Of related interest, there seems to be an interest for non invasive capabilities, this one is tough one.

Do the sensors have to be wireless?
No; however, due to consumer experience requirements it's unlikely a non-wireless sensor will be successful.

Can the sensors be invasive? (What is "invasive?")
There is no requirement or limit on sensing; we define a grand challenge and let teams find the best, innovative new solutions. "Invasive" means it punctures the skin. The competition allows this but it's very unlikely this would be acceptable to a consumer. For example, drawing blood is invasive but the accelerometer in your phone is non-invasive.

Finally, when they talk about sensing, they really mean sensing and make sense of it:

What is the difference between sensors and sensing? (What is "sensing?")
Sensors are generally physical hardware. These are used to collect health metrics and data about a person. The sensor can collect data for a short or long period of time. Sensing is the process of taking the data and interpreting it for patterns. These patterns can be analyzed to show unusual variations within one person, or compared to other people.

From the compressive sensing standpoint, there are obvious subjects of interest in this description, some of which have somehow already been implemented by some research teams. However, besides ECG, EEG, there might be some trickier inverse problems if we want to avoid the issue of non invasiveness. In particular, there may be a need for the fusion of inverse problems that generally are not considered together.

I would be interested in being part of a team that competes in this challenge. I may contact some of you in the future on the matter but if you want to just talk about it, we can do that as well. Obviously, all these discussions will remain private unless we, both parties, agree to communicate on these matters. Wave me in if interested.

.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Request for Expression of Interest: The Qualcomm Tricorder X Prize

2012-01-13T07:41:00.002-06:00

The Qualcomm Tricorder X Prize was announced at CES this week. The goal of the competition is to build a "thing" that can

".....capable of capturing key health metrics and diagnosing a set of 15 diseases. Metrics for health could include such elements as blood pressure, respiratory rate, and temperature. Ultimately, this tool will collect large volumes of data from ongoing measurement of health states through a combination of wireless sensors, imaging technologies, and portable, non-invasive laboratory replacements...".

"....What's new about the technology? Doesn't most of this already exist?
Yes, some of the technology exists today. However, the the teams in this competition will pull this all together in one seamless system. The resulting instrument will also push the sensing component of technology in different ways: Smaller, lighter, cheaper, faster, better. Integration of these many different components is expected to be very challenging...."

While the emphasis is on diagnostics, I note the importance of continuous monitoring

What will the Device actually do?

Diagnose diseases

Provide ongoing metrics of health (vitals)

Allow monitoring or continuous use of sensors to diagnose and measure health

Provide awareness of health state

Give confirmation that everything is ok with a consumer

Notify that something is not ok (a "check engine light")

Of related interest, there seems to be an interest for non invasive capabilities, this one is tough one.

Do the sensors have to be wireless?
No; however, due to consumer experience requirements it's unlikely a non-wireless sensor will be successful.

Can the sensors be invasive? (What is "invasive?")
There is no requirement or limit on sensing; we define a grand challenge and let teams find the best, innovative new solutions. "Invasive" means it punctures the skin. The competition allows this but it's very unlikely this would be acceptable to a consumer. For example, drawing blood is invasive but the accelerometer in your phone is non-invasive.

Finally, when they talk about sensing, they really mean sensing and make sense of it:

What is the difference between sensors and sensing? (What is "sensing?")
Sensors are generally physical hardware. These are used to collect health metrics and data about a person. The sensor can collect data for a short or long period of time. Sensing is the process of taking the data and interpreting it for patterns. These patterns can be analyzed to show unusual variations within one person, or compared to other people.

OSTP RFI Last day for comments, Around the blogs in 80 hours and Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation

2012-01-12T03:10:00.000-06:00

Various items on the block today:

First Today is the last for getting your throughts to two Request For Information by the Office of Science and Technology Policy:

I expressed my view on the former in Toward Robust Science: Why Open Access of Government Funded Peer Review Work is Important but it could rightly apply to the latter as well. I listed the questions here.

"...How To Submit a Response All comments must be submitted electronically to: publicaccess@ostp.gov. Responses to this RFI will be accepted through January 12, 2012. You will receive an electronic confirmation acknowledging receipt of your response,..."

Please note that you do not have to be a US person to submit a response. Also note that any information (that includes your identity) will be a matter of public record as normally expected in this type of generic inquiry. You can still make your submission anonymous if this is bothering you.

I will not be watching the presentations at MIA 2012 but I may or may not drop in in the cafeteria next door in between some presentations for the coffee breaks.. I removed myself from the list of participants early on so that younger participants could have a chance to attend and learn. Gabriel, one of the organizers, told me that more than 300 people applied but that the rooms at IHP could only safely host 200 or so folks. Congratulations to the organizers, it looks like it will be an impressive series of talks with a large audience.

On LinkedIn, someone asked Does anybody know how to implement compressive sensing in simulink? and another I'm building a compressed sensing Receiver for UWB signals...do You know how to construct the matrices using amplifiers?... Also, Ruiliang Zhang provided an answer to What's the most important paper to deal with Bregman iteration?

Rich mentioned the upcoming Connexions conference, Bob talks about Strange behavior in sparse representation classification?, Zhilin provides some information on his new paper (see his email below for more information). Danny provides us with a Vowpal Wabbit Tutorial. Terry reviews Random matrices and specifically The Four Moment Theorem for Wigner ensembles. Here is a review of Persi Diaconis' latest book in the WSJ , I am going to get it on the Kindle app for the iPhone/iPad,

At UBC there are two courses related to compressed sensing: MATH 555 taught by Ozgur Yilmaz and

EOSC 513 taught by Felix Hermann. Ar University of Michigan, Anna Gilbert has a blog where she writes down some of her lectures there. At Iowa State, Namrata Vaswani teaches EE 527: Detection and Estimation Theory with relevant parts related to compressive sensing.

Justin Romberg's lectures at ENS Lyon last week just showed up on the interwebs::

lecture-1-1-basis.pdf

lecture-1-2-frames.pdf

lecture-1-3-dct-notes.pdf

lecture-1-4-wavelets.pdf

lecture-1-5-sparsity-overview.pdf

lecture-2-1-sparseapprox.pdf

lecture-2-2-bp.pdf

lecture-2-3-upsparse.pdf

lecture-2-4-1-csoverview.pdf

lecture-2-4-1-csoverview1.pdf

lecture-2-4-2-csoverview.pdf

lecture-2-4-3-csoverview.pdf

lecture-2-4-4csoverview.pdf

lecture-3-1-invprobs.pdf

lecture-3-2-ls.pdf

lecture-3-3-l1dual.pdf

lecture-3-4-l1cone.pdf

lecture-3-5-stable.pdf

lecture-4-1-gaussrip.pdf

notation.pdf

At the Joint Mathematics Meeting, Eric Price gave a talk on the Geometric Aspects of Compressive Sensing

Knome Expands Scientific Advisory Board and brings Dr. Yaniv Erlich bring genomics expertise as company pursues future growth

Finally, Zhilin Zhang sent me the following:

".....Hi, Igor,

....We just submitted a paper on block sparse model, which considers to exploit intra-block correlation:, Zhilin Zhang, Bhaskar D. Rao , Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation, submitted to IEEE Transaction on Signal Processing, January 2012. The preprint can be downloaded here: http://arxiv.org/abs/1201.0862. Here is the abstract:

We examine the recovery of block sparse signals and extend the framework in two important directions; one by exploiting intra-block correlation and the other by generalizing the block structure. We propose two families of algorithms based on the framework of block sparse Bayesian learning (bSBL). One family, directly derived from the bSBL framework, requires knowledge of the block partition. Another family, derived from an expanded bSBL framework, is based on a weaker assumption about the a priori information of the block structure, and can be used in the cases when block partition, block size, block sparsity are all unknown. Using these algorithms we show that exploiting intra-block correlation is very helpful to improve recovery performance. These algorithms also shed light on how to modify existing algorithms or design new ones to exploit such correlation for improved performance.

Please note that:

Our proposed algorithms have the best recovery performance among ALL the existing algorithms (I've sent more than one month to carry out experiments to compare algorithms, but didn't find any algorithms have the similar performance as ours).
These algorithms are the first algorithms that adaptively exploit intra-block correlation.
We revealed that intra-block correlation, if exploited, can significantly improve recovery performance. I think you may not be surprised by this observation, since we obtained similar observation from our previous MMV work (i.e. temporal correlation, if exploited, can significantly improve recovery performance of MMV algorithms)
But interestingly, we found that the intra-block correlation has little effects on the performance of existing algorithms. This observation is entirely different to our previous finding on the MMV model, where we found temporal correlation has obvious negative effects on the performance of existing algorithms. For example, group Lasso keeps almost the same recovery performance no matter what's the intra-block correlation value. I guess maybe this is the reason that why intra-block correlation has not drawn attention from the people working on the block sparse model. But as you can see from our paper, exploiting the intra-block correlation can be very helpful to improve recovery performance (or reduce the number of measurements with the same recovery performance).

The codes will be posted on the website: http://dsp.ucsd.edu/~zhilin/BSBL.html (probably at the end of this month). But any one, if interested in, can send email to me to get these codes...."

Thanks Zhilin for the heads-up.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Implementation for the Generalization of the Column-Row Matrix Decomposition to Multi-way Arrays

2012-01-11T00:01:00.000-06:00

Cesar Caiafa sent me the following:

Dear Igor;

My name is Cesar Caiafa, some time ago I found your excellent blog with very useful and important references to works on Compressed Sensing and more recently, about matrix factorization (MF) and low rank approximations which is one of my research interests.

One of the generalizations of MF are tensor factorizations, in particular, one of the possible tensor factorizations is the Tucker model used for multiway data since long time ago.

I would like to drive your attention to our work from 2010 in Linear Algebra and Its applications:

“Generalizing the Column-Row Matrix Decomposition to Multi-way Arrays”, Cesar F. Caiafa, A. Cichocki, Linear Algebra and its Applications, Vol. 433, pp. 557–573, 2010 (Elsevier).

In this paper, we developed new formulas and algorithms to compute a compressed format of an N-way tensor based only on the information contained in few selected n-mode fibers, i.e. for a 3D tensor, we are able to approximate it based on the entries on few columns (1-mode), rows (2-mode) and tubes (3-modes). We called this method as Fiber Sampling Tensor Decomposition (FSTD). Our idea was motivated by several previous works by M Mahoney, P. Drineas, I. Oseledets and E. Tyrtyshnikov. The abstract reads as follows:

"In this paper, we provide two generalizations of the CUR matrix decomposition Y=CUR (also known as pseudo-skeleton approximation method [1]) to the case of N-way arrays (tensors). These generalizations, which we called Fiber Sampling Tensor Decomposition types 1 and 2 (FSTD1 and FSTD2), provide explicit formulas for the parameters of a rank-(R,R,…,R) Tucker representation (the core tensor of size R×R×⋯×R and the matrix factors of sizes In×R, n=1,2,…N) based only on some selected entries of the original tensor. FSTD1 uses PN-1(P⩾R)n-mode fibers of the original tensor while FSTD2 uses exactly R fibers in each mode as matrix factors, as suggested by the existence theorem provided in Oseledets et al. (2008) [2], with a core tensor defined in terms of the entries of a subtensor of size R×R×⋯×R. For N=2 our results are reduced to the already known CUR matrix decomposition where the core matrix is defined as the inverse of the intersection submatrix, i.e. U=W-1. Additionally, we provide an adaptive type algorithm for the selection of proper fibers in the FSTD1 model which is useful for large scale applications. Several numerical results are presented showing the performance of our FSTD1 Adaptive Algorithm compared to two recently proposed approximation methods for 3-way tensors."

The preprint of our paper is available at

http://web.fi.uba.ar/~ccaiafa/preprints/TensorCUR_v6.pdf

Also Matlab codes for FSTD are available at

http://web.fi.uba.ar/~ccaiafa/Code/FSTD1_package.rar

You can share this information if you like.

Best Regards

Cesar

http://web.fi.uba.ar/~ccaiafa/Cesar/Cesar.html

Thank you Cesar.

Algorithm		Complexity	Sparsity Range
sFFT 1.0 (Non-Iterative Alghorithm)	::
sFFT 2.0 (sFFT 1.0 + Heuristic)	::
sFFT 3.0 (Exact k Sparse Algorithm)	::
sFFT 4.0 (General k Sparse Algorithm)	::
Lower Bound	::