Saturday, April 19, 2014

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 )


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.

Friday, April 18, 2014

You are not paying attention if...





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.
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.

Thursday, April 17, 2014

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.

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 ]


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.


Wednesday, April 16, 2014

3000th post. Wow !




So, this is the 3000th published post. wow! While there is nothing magic about this number, here is some perspective: it's about ten times 300 posts, or roughly the equivalent of 10 years of constant weekly posting and then some week-ends. I went from being ignorant about many things to having the blog mentioned in different quarters of the academic world. Let's not forget that one of the realities of the relative success of Nuit Blanche stems from the broken publishing model. On top of not providing quality peer review, the publishing cycle only allows relentless (most have no choice but being relentless) authors to be published. Using the Google, some of my own spidering processes and more recently ArXiv, Nuit Blanche features ideas and authors, two to three years ahead of the publishing cycle. Anybody who wants to have a headstart and be productive is bound to use it as one of its source of information. Without getting into the detail of it, the blog has followed the maturation of a field. There is yet so much to see since the blog follows the unfolding of the different crafts involved in sensing and making sense of what is sensed. That story keeps on giving. You want to show your appreciation ? Don't hesitate to provide a recommendation on LinkedIn under my profile. Seven other readers have done so in the past. By adding one, you are sending a signal that this type of academic blogging is serious and highly relevant while at the same time bringing clarity. When being asked outside of this community about Nuit Blanche, I find it difficult to articulate how relevant it is. Your recommendations are sending this louder signal that it is relevant. 

In the meantime, here are some links that have blossomed here over the past fast few years.
  • CS (1870): All blog entries related to compressive sensing
  • MF (293): All blog entries related to advanced matrix factorizations
  • implementation (234): All blog entries related to an implementation made available by their authors
  • CSHardware (80): All blog entries related to compressive sensing hardware and sensors.
  • CSjobs (69): All blog entries related to compressive sensing related jobs.
  • SundayMorningInsight (37): All blog entries featuring some Sunday Morning Reviews of something that has to be said :-)
  • ML (54): All blog entries related to Machine Learning
  • Csstats (22): All blog entries related to the blog entries featuring statistique on the coming and goings on this site.
The blog has more than +122 Google+1s

Several groups have emerged

But also several reference pages: 

Tuesday, April 15, 2014

Recent Developments in the Sparse Fourier Transform: A Fast DSP Chip and a faster GPS

A 0.75-million-point fourier-transform chip for frequency-sparse signals by Omid Abari, Ezz Hamed, Haitham Hassanieh, Abhinav Agarwal, Dina Katabi, Anantha P. Chandrakasan, Vladimir Stojanovic
Applications like spectrum sensing, radar signal processing, and pattern matching by convolving a signal with a long code, as in GPS, require large FFT sizes. ASIC implementations of such FFTs are challenging due to their large silicon area and high power consumption. However, the signals in these applications are sparse, i.e., the energy at the output of the FFT/IFFT is concentrated at a limited number of frequencies and with zero/negligible energy at most frequencies. Recent advances in signal processing have shown that, for such sparse signals, a new algorithm called the sparse FFT (sFFT) can compute the Fourier transform more efficiently than traditional FFTs [1].


Faster GPS Via the Sparse Fourier Transform  by Haitham Hassanieh, Fadel Adib, Dina Katabi, and Piotr Indyk. ( Slides )
GPS is one of the most widely used wireless systems. A GPS re ceiver has to lock on the satellite signals to calculate its position. The process of locking on the satellites is quite costly and requires hundreds of millions of hardware multiplications, leading to high power consumption. The fastest known algorithm for this problem is based on the Fourier transform and has a complexity of O(nlogn), where n is the number of signal samples. This paper presents the fastest GPS locking algorithm to date. The algorithm reduces the locking complexity to O(n√logn). Further, if the SNR is above a threshold, the algorithm becomes linther, if the SNR is above a threshold, the algorithm becomes linear, i.e., O(n). Our algorithm builds on recent developments in the growing area of sparse recovery. It exploits the sparse nature of the synchronization problem, where only the correct alignment btween the received GPS signal and the satellite code causes their cross-correlation to spike. We further show that the theoretical gain translates into empirical gains for GPS receivers. Specifically, we built a prototype of the design using software radios and tested it on two GPS datasets collected in the US and Europe. The results show that the new agorithm reduces the median number of multiplications by 2.2× in comparison to the state of the art design, for real GPS signals.


these examples of applications were found in this Recent Developments in the Sparse Fourier Transform by Anna C. Gilbert, Piotr Indyk, Mark Iwen, Ludwig Schmidt

The Discrete Fourier Transform (DFT) is one of the most important discrete transformations used in many computational settings from signal or image processing to scienti c computing. The most popular approach to computing the DFT uses the Fast Fourier Transform (FFT). However, with the emergence of big data problems, in which the size of the processed data sets can easily exceed terabytes, the \Fast" in Fast Fourier Transform is not fast enough. Furthermore, in many big data applications it is hard to acquire a su cient amount of data to compute the desired Fourier transform. The Sparse Fourier Transform (SFT) can compute a compressed Fourier transform using only a subset of the input data in time considerably shorter than the data set size. The goal of this article is to survey these recent developments, to explain the basic techniques coupled with examples and applications in big data, to demonstrate trade-o ffs in empirical performance of the algorithms, and to discuss the connection between the SFT and other techniques for massive data analysis such as streaming algorithms and compressive sensing.
An implementation of the sFFT is here. Other implementations are available under the FFT tag.

Monday, April 14, 2014

Compressive classification and the rare eclipse problem

This is interesting !

Compressive classification and the rare eclipse problem by Afonso S. Bandeira, Dustin G. Mixon, Benjamin Recht
This paper addresses the fundamental question of when convex sets remain disjoint after random projection. We provide an analysis using ideas from high-dimensional convex geometry. For ellipsoids, we provide a bound in terms of the distance between these ellipsoids and simple functions of their polynomial coefficients. As an application, this theorem provides bounds for compressive classification of convex sets. Rather than assuming that the data to be classified is sparse, our results show that the data can be acquired via very few measurements yet will remain linearly separable. We demonstrate the feasibility of this approach in the context of hyperspectral imaging.



from the conclusion:

It is also interesting how similar random projection and PCA perform. Note that the PCA method has an unfair advantage since it is data-adaptive, meaning that it uses the training data to select the projection, and in practical applications for which the sensing process is expensive, one might be interested in projecting in a non-adaptive way, thereby allowing for less sensing. Our simulations suggest that the expense is unnecessary, as a random projection will provide almost identical performance. As indicated in the previous subsection, random projection is also better understood as a means to maintain linear separability, and so there seems to be little bene t in choosing PCA over random projection (at least for this sort of classi cation task).
and this

As such, it would be interesting to extend the results of this paper to more general classes of random projections, in particular, random projections which can be implemented with a hyperspectral imager (say).

Maybe, we could try random projections as instantiated by Nature.



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.

Confidence Intervals and Hypothesis Testing for High-Dimensional Regression - implementation -

As we were discussing the release of an implementation of the Sparse PCA algorithm, Andrea mentioned to me the release of an R program for hypothesis testing with the Lasso:


Fitting high-dimensional statistical models often requires the use of non-linear parameter estimation procedures. As a consequence, it is generally impossible to obtain an exact characterization of the probability distribution of the parameter estimates. This in turn implies that it is extremely challenging to quantify the uncertainty associated with a certain parameter estimate. Concretely, no commonly accepted procedure exists for computing classical measures of uncertainty and statistical significance as confidence intervals or p-values for these models. We consider here high-dimensional linear regression problem, and propose an efficient algorithm for constructing confidence intervals and p-values. The resulting confidence intervals have nearly optimal size. When testing for the null hypothesis that a certain parameter is vanishing, our method has nearly optimal power. Our approach is based on constructing a ‘de-biased’ version of regularized M-estimators. The new construction improves over recent work in the field in that it does not assume a special structure on the design matrix. We test our method on synthetic data and a high-throughput genomic data set about riboflavin production rate, made publicly available by [BKM14].

A web page, maintained by Hamid Javadi, Adel JavanmardAndrea Montanari and Sven Schmit, featuring other papers and an implementation in R is here.



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.