Low-Rank Modeling of Local k-Space Neighborhoods (LORAKS): Implementation and Examples for Reproducible Research

Justin Haldar just sent me the following:

Hi Igor,

Wanted to let you know that we've finally put out the public release of the LORAKS code (that you featured on Nuit Blanche back in December). There is a technical report that describes the implementation and walks through all of the examples included with the code available here:

http://sipi.usc.edu/reports/abstracts.php?rid=sipi-414

The tech report (and the corresponding demo code) build on the original published LORAKS paper, showing several more examples (including one multi-band signal reconstruction example that is outside the MRI context for which LORAKS was originally designed, and which I think is pretty nea).

The code itself is available here:

http://mr.usc.edu/download/LORAKS

Cheers!

--

Justin Haldar

Signal and Image Processing Institute

Electrical Engineering and Biomedical Engineering

University of Southern California

http://mr.usc.edu/

Thanks Justin. Here is the paper: Low-Rank Modeling of Local k-Space Neighborhoods (LORAKS): Implementation and Examples for Reproducible Research by Justin Haldar

Our recent work has introduced a new signal processing framework that enables the recovery of magnetic resonance (MR) images from undersampled and/or noisy Fourier data, based on the assumptions that the true image has smooth phase and/or limited spatial support. This framework, named LORAKS, relies on embedding the Fourier data from such images into high-dimensional Hankel-like matrices, which we showed would have approximately low rank when the phase/support assumptions were satisfied. The fact that these matrices have low rank implies that they have relatively few degrees of freedom relative to their number of entries, and hence can potentially be recovered from subsampled data. In contrast to conventional reconstruction methods that rely on assumptions of smooth image phase and/or limited spatial support, LORAKS does not place strict requirements on the sampling scheme used for data acquisition, and high-quality reconstructions can be obtained from both highly-structured and highly-unstructured Fourier sampling schemes. In contrast to other recent MR image reconstruction methods based on low-rank modeling, LORAKS can be used with relatively low-dimensional single-channel, single-contrast, single-timepoint MR imaging data. We have also previously demonstrated that LORAKS has distinct features and advantages relative to sparsity-based MR image reconstruction methods (which have been receiving substantial attention over the past several years), which suggests that phase and support constraints can be used in combination with sparsity constraints for even better performance.
In the spirit of reproducible research, this technical report (and corresponding supplementary material available for download at http://mr.usc.edu/download/LORAKS/) provides a MATLAB implementation of a LORAKS-based reconstruction algorithm proposed in our previous work, and presents several application examples that are not found in the existing literature (including an example outside the context of MR imaging).

Join the CompressiveSensing subreddit or the Google+ Community and post there !

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.

PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations - implementation -

I mentioned this paper before but now there is a newer version and most importantly, an implementation.

PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations by Yuejie Chi, Yonina C. Eldar, Robert Calderbank

Many real world data sets exhibit an embedding of low-dimensional structure in a high-dimensional manifold. Examples include images, videos and internet traffic data. It is of great significance to reduce the storage requirements and computational complexity when the data dimension is high. Therefore we consider the problem of reconstructing a data stream from a small subset of its entries, where the data is assumed to lie in a low-dimensional linear subspace, possibly corrupted by noise. We further consider tracking the change of the underlying subspace, which can be applied to applications such as video denoising, network monitoring and anomaly detection. Our problem can be viewed as a sequential low-rank matrix completion problem in which the subspace is learned in an on-line fashion. The proposed algorithm, dubbed Parallel Estimation and Tracking by REcursive Least Squares (PETRELS), first identifies the underlying low-dimensional subspace via a recursive procedure for each row of the subspace matrix in parallel with discounting for previous observations, and then reconstructs the missing entries via least-squares estimation if required. Numerical examples are provided for direction-of-arrival estimation and matrix completion, comparing PETRELS with state of the art batch algorithms.

The implementation is on Yuejie Chi's publication page.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Random forests with random projections of the output space for high dimensional multi-label classification

It started in 2009 when John Langford and colleagues noted that label vectors were sparse and that using techniques of compressive sensing one could reduce learning in large dimensional space. Here is a new entrant in this area:

Random forests with random projections of the output space for high dimensional multi-label classification by Arnaud Joly, Pierre Geurts, Louis Wehenkel

We adapt the idea of random projections applied to the output space, so as to enhance tree-based ensemble methods in the context of multi-label classification. We show how learning time complexity can be reduced without affecting computational complexity and accuracy of predictions. We also show that random output space projections may be used in order to reach different bias-variance tradeoffs, over a broad panel of benchmark problems, and that this may lead to improved accuracy while reducing significantly the computational burden of the learning stage.

I note the following

On the other hand, since we are not concerned in this paper with the ‘reconstruction’ problem, we do not need to make any sparsity assumption ‘à la compressed sensing’.

This is all good, but if it works, then attempts like references [3] might be helped further because I don't fully buy that argument. It is not because you don't need a sparsity seeking reconstruction solver that the underlying assumption isn't there as used in [1,2].

Other references of interest: 

1. Multi-Label Prediction via Compressed Sensing by Daniel Hsu, Sham M. Kakade, John Langford, Tong Zhang (attendant slides )
2. Robust Bloom Filters for Large MultiLabel Classification Tasks by Moustapha M Cisse, Nicolas Usunier, Thierry Artières, Patrick Gallinari
3. Narrowing the Gap: Random Forests In Theory and In Practice by Misha Denil, David Matheson, Nando de Freitas
4. Compact Representations for “Large-scale” Computation by Vidit Jain

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Sunday Morning Insight: Why You Should Care About Phase Transitions in Clustering

Figure from [1]

In the Advanced Matrix Factorization page, I have no listing for the phase transition section of the spectral clustering or its nonlinear cousin subspace clustering. Little did I know that Suresh Venkatasubramanian (from the GeomBlog fame) has written about it in his essay on clustering. In particular, he wrote this interesting entry entitled: Choosing the number of clusters III: Phase Transitions where he draws a connection with statistical physics

...How can you tell when this happens ? Here's a very elegant technique, first proposed by Kenneth Rose in his work on deterministic annealing. In the high-T regime, where every point is in the same cluster, the cluster center location can be computed by solving a simple convex optimization. As the process evolves, the positive definite matrix defining the optimization starts losing its positive definiteness, till some point when one of its eigenvalues goes to zero. This point can be computed analytically, and yields a specific temperature value at which the first clusters start to emerge.
Kenneth Rose has some nice examples illustrating this behaviour. As time goes one, more and more phase transitions start to appear, as more and more clusters start to emerge. What you end up with is a hierarchy of clusterings that end with the trivial clustering where all data lie in separate clusters.
This idea has been developed further with the information bottleneck method, which replaces both the distortion and entropy terms by terms involving the mutual information of the assignments. The free energy paradigm works the same way, although now the phase transition points can't be computed analytically (I'll have more to say about the information bottleneck method)
What's entirely weird is that the phase transitions still happen (and I want to stress this point), data sets will split up into different numbers of clusters at the same transition point ! We wrote a paper a few years ago that proposes a particular "temperature" to look for phase transitions in, and lo and behold, we were able to recover the "correct" number of clusters from planted data sets by watching the data split at this point. I'm still not sure why this happens, but it was quite interesting, and yielded one way of identifying "natural clusters" in the data....

from Albert Parker's Ph.D thesis [3]

which leads me to Lenka Zdeborova's presentation at Paris Machine Learning Meetup #8 ( How hard is it to find a needle in a haystack? ) who tells a similar story of a connection between statistical physics and clustering [4,5,6] in finding communities within large sparse networks. In particular, she and co-authors also describe, the non-backtracking matrix a better choice for the transformation of the data/graph representation than the Laplacian or the adjacency matrix [5].

Why should we care ? because as Adam Coates and Andrew Y. Ng stated recently in [7], these clustering algorithms, much like dictionary learning in the early deep neural network papers are the first steps for feeding data into some deep learning algorithms. From [7]:

...Recently, it has been found that K-means clustering can be used as a fast alternative training method. The main advantage of this approach is that it is very fast and easily implemented at large scale. On the other hand, employing this method in practice is not completely trivial: K-means has several limitations, and care must be taken to combine the right ingredients to get the system to work well...

This must be balanced against a more recent shift on data that Sander Dieleman, a redditor and the winner of the recent Kaggle competition on the Galaxy Challenge, identified in a recent Reddit thread :

...I still see plenty of questions on Metaoptimize, on the Deep Learning G+ community, on the Kaggle forums and on this subreddit, from people who seem to be unaware of this "paradigm shift". They ask about training autoencoders and RBMs for unsupervised feature learning, when it is often clear that a purely supervised approach would probably work at least as well for their problem (and is conceptually much simpler and easier to understand).

I think this is because they read papers from 2010-2012 advertising unsupervised pre-training as the holy grail of deep learning. That was only 2-4 years ago, so they can't really be blamed for assuming that this approach still represents the state of the art.

Of course unsupervised pre-training still has its applications, but for many problems it has been obsoleted. So I don't think it's a bad thing to draw some attention to this fact

so quite clearly supervised learning applications in human speech or images won't need much clustering like K-means/subspace clustering but it will remain key for real exploration like understanding Dolphin communication or learning heterogenous data among other. And as the map makers did in compressive sensing, those phase transitions, when they are identified, will be key to understand these data. Given a dataset, if these algorithms fail (i.e are not robust) in these unsupervised settings, then you are either not catching the right data (and need to expand them by making the network less sparse) or you are not using the right modeling tools (metric, ...) .

PS: All these phase transitions results appear for spectral clustering and none seem to have been found in the subspace clustering arena .... yet.

PPS: I'll add this blog entry to the phase transition of the Spectral Clustering section in the Advanced Matrix Factorization Jungle page. I just split the spectral clustering section from the subspace clustering one and came up with this division:

• Spectral Clustering, A = DX with unknown D and X, solve for sparse X and X_i = 0 or 1 
• Subspace Clustering, A = AX with unknown X, solve for sparse/other conditions on X 

[1] Generative-Discriminative Basis Learning for Medical Imaging by Nematollah K. Batmanghelich, Ben Taskar, Christos Davatzikos. 

[2] How many clusters? An information theoretic perspective by Susanne Still, William Bialek

[3] Symmetry Breaking Bifurcations of the Information Distortion by Albert Edward Parker III

[4] Phase transition in the detection of modules in sparse networks by Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborová

[5] Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications by Aurelien Decelle, Florent Krzakala, Cristopher Moore, Lenka Zdeborová

[6] Spectral redemption: clustering sparse networks by Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, Pan Zhang

[7] Learning Feature Representations with K-means, Adam Coates and Andrew Y. Ng

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Saturday Morning Videos: ICLR Videos and Papers

The folks at ICLR 2014 are releasing videos of the meeting. The whole channel of the meeting is here. Here is a sampling of interest with attendant reviews and papers:

  ICLR 2014 Talk: "Revisiting Natural Gradient for Deep Networks" by Razvan Pascanu and Yoshua Bengio. Attendant review of the paper.      ICLR 2014 Talk: "Exact solutions to the nonlinear dynamics of learning in deep linear neural networks" by Andrew M. Saxe, James L. McClelland, Surya Ganguli Attendant review of the paper       ICLR 2014 Talk:  Zero-Shot Learning by Convex Combination of Semantic Embeddings, Mohammad Norouzi, Tomas Mikolov, Samy Bengio, Yoram Singer, Jonathon Shlens, Andrea Frome, Greg S. Corrado,  Jeffrey Dean.      ICLR 2014 Workshop Talk: "Unsupervised Feature Learning by Deep Sparse Coding" Yunlong He, Koray Kavukcuoglu, Yun Wang, Arthur Szlam, Yanjun Qi.     Relaxations for inference in restricted Boltzmann machines, Sida I. Wang, Roy Frostig, Percy Liang, Christopher D. Manning      ICLR 2014 Talk: "Group-sparse Embeddings in Collective Matrix Factorization" by Arto Klami, Guillaume Bouchard, Abhishek Tripathi Review of the paper    ICLR 2014 Talk: "Auto-Encoding Variational Bayes" by Diederik P. Kingma, Max Welling. Review of the paper    ICLR 2014 Talk: OverFeat: Integrated Recognition, Localization and Detection using Convolutional Networks by Pierre Sermanet, David Eigen, Xiang Zhang, Michael Mathieu, Rob Fergus, Yann LeCun Review of the paper.    ICLR 2014 Talk: "Learning Transformations for Classification Forests" by Qiang Qiu, Guillermo Sapiro Review of the paper.       ICLR 2014 Talk: "Sparse similarity-preserving hashing, Jonathan Masci, Alex M. Bronstein, Michael M. Bronstein, Pablo Sprechmann, Guillermo Sapiro Review of the paper.   ICLR 2014 Talk: "" by Ian J. Goodfellow, Yaroslav Bulatov, Julian Ibarz, Sacha Arnoud, Vinay Shet Review of the paper    ICLR 2014 Talk: "Spectral Networks and Locally Connected Networks on Graphs" by Joan Bruna, Wojciech Zaremba, Arthur Szlam, Yann LeCun Review of the paper.


Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Saturday Morning Video: Learning Visual Representations at Scale, Vincent Vanhoucke

Learning Visual Representations at Scale by Vincent Vanhoucke (another presentation that features
Deep ConvNets; "Astounding" baseline for vision )

in the meantime, ccv 0.6 open sources near state-of-the-art image classifier under Creative Commons

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

You are not paying attention if...

• you believe speckle is noise,
• your internet of things gadget does not have a camera,
• your business depends on making sense of camera data and you don't know about OverFeat, Caffe or ccv,
• you believe compressive sensing is niche,
• you believe that random projections are inferior to PCA,
• you believe an algorithm implementation is the same as the algorithm itself
• you believe sensor design has little to do with Machine Learning
• you are a privacy protection agency and you are not investing in real research
• .... To be continued

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Privacy Tradeoffs in Predictive Analytics

Here is something new in the privacy game that relies on the fact that most matrix factorization in the recommender system business are low rank. From the paper:

To the best of our knowledge, we are the first to take into account the data disclosed by an analyst in the above privacy-accuracy tradeo , and to establish the optimality of a combined disclosure, obfuscation, and prediction scheme. Our proofs rely on the modeling assumption that is the cornerstone of matrix factorization techniques and hence validated by vast empirical evidence (namely, that the user-item ratings matrix is approximately low-rank). Moreover, the fact that our algorithms successfully block inference against a barrage of di erent classifi ers, some non-linear, further establishes our assumption's validity over real-world data.

Here is the paper: Privacy Tradeoffs in Predictive Analytics by Stratis Ioannidis, Andrea Montanari, Udi Weinsberg, Smriti Bhagat, Nadia Fawaz, Nina Taft

Online services routinely mine user data to predict user preferences, make recommendations, and place targeted ads. Recent research has demonstrated that several private user attributes (such as political affiliation, sexual orientation, and gender) can be inferred from such data. Can a privacy-conscious user benefit from personalization while simultaneously protecting her private attributes? We study this question in the context of a rating prediction service based on matrix factorization. We construct a protocol of interactions between the service and users that has remarkable optimality properties: it is privacy-preserving, in that no inference algorithm can succeed in inferring a user's private attribute with a probability better than random guessing; it has maximal accuracy, in that no other privacy-preserving protocol improves rating prediction; and, finally, it involves a minimal disclosure, as the prediction accuracy strictly decreases when the service reveals less information. We extensively evaluate our protocol using several rating datasets, demonstrating that it successfully blocks the inference of gender, age and political affiliation, while incurring less than 5% decrease in the accuracy of rating prediction.

of related interest: The Simons Institute's recent Big Data and Differential Privacy workshop.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Robust Subspace Recovery via Dual Sparsity Pursuit

The implementation for this solver is not available, here is another phase diagram for the Robust PCA decomposition. 

the previous one is featured in the Advanced Matrix Factorization Jungle page from Bilinear Generalized Approximate Message Passing by Jason T. Parker, Philip Schniter, Volkan Cevher. One wonders how the two diagrams fit with each other. Here is the paper: Robust Subspace Recovery via Dual Sparsity Pursuit by Xiao Bian, Hamid Krim

Successful applications of sparse models in computer vision and machine learning imply that in many real-world applications, high dimensional data is distributed in a union of low dimensional subspaces. Nevertheless, the underlying structure may be affected by sparse errors and/or outliers. In this paper, we propose a dual sparse model as a framework to analyze this problem and provide a novel algorithm to recover the union of subspaces in presence of sparse corruptions. We further show the effectiveness of our method by experiments on both synthetic data and real-world vision data.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.

Non-invasive real-time imaging through scattering layers and around corners via speckle correlations

Wow !

Several themes mentioned in this blog are colliding in the following preprint. First thanks to the Moore's law we have the ability to do high resolution imagery with smartphone cameras like the Lumia 1020. Then there is this imaging with nature theme and then there is the sparse phase retrieval problem. I say sparse but there is no connection to that in this preprint and much like FROG (see here and here also), time will tell. What is so interesting here is that there is no need to know the transmission matrix or even the need for a time of flight cameras to see around the corners: A smartphone camera is all you need.

On a more general note, those quantum optic problems seem to have solutions for sparse imaging but there isn't much of a literature on the subject, in particular, since everybody is focused on correlation type of imaging, other types of nonlinearities such as triple correlation interferometry seem to be left on their own device (see the vocabulary used here and here). Anyway, enjoy!

[ and by the way, no, the speckle is not the problem, it was, and continues to be the solution ]

Non-invasive real-time imaging through scattering layers and around corners via speckle correlations by Ori Katz, Pierre Heidmann, Mathias Fink, Sylvain Gigan

Imaging with optical resolution through and inside complex samples is a difficult challenge with important applications in many fields. The fundamental problem is that inhomogeneous samples, such as biological tissues, randomly scatter and diffuse light, impeding conventional image formation. Despite many advancements, no current method enables to noninvasively image in real-time using diffused light. Here, we show that owing to the memory-effect for speckle correlations, a single image of the scattered light, captured with a standard high-resolution camera, encodes all the information that is required to image through the medium or around a corner. We experimentally demonstrate single-shot imaging through scattering media and around corners using incoherent light and various samples, from white paint to dynamic biological samples. Our lensless technique is simple, does not require laser sources, wavefront-shaping, nor time-gated detection, and is realized here using a camera-phone. It has the potential to enable imaging in currently inaccessible scenarios.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
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.