Friday, July 25, 2014

It's Friday afternoon, it's Hamming's time: Higher Order Antipode Maps ?






Could the second map be roughly approximated through the use of correlation between zero-th, first and higher order harmonic on the sphere ?


Last Call for Contributions - TCMM 2014 International Workshop on Technical Computing for Machine Learning and Mathematical Engineering, 8 - 12 September, 2014 - Leuven, Belgium


Marco just sent me the following:

Dear Igor,
could you be so kind to post the attached CFP  (last call for contributions - TCMM 2014) on Nuit Blanche?
kind regards
Marco
--
dr. Marco Signoretto
FWO research fellow,
ESAT - STADIUS,
Katholieke Universiteit Leuven,
Kasteelpark Arenberg 10, B-3001 LEUVEN - HEVERLEE (BELGIUM)
Homepage: http://homes.esat.kuleuven.be/~msignore/
Sure Marco, here is the call:
                                                                     
                                                                     
                                                                     
                                             
Last Call for Contributions - TCMM 2014 International Workshop on Technical Computing for Machine Learning and Mathematical Engineering
8 - 12 September, 2014 - Leuven, Belgium
Workshop homepage: http://www.esat.kuleuven.be/stadius/tcmm2014/
The workshop will provide a venue for researchers and practitioners to interact on the latest developments in technical computing in relation to machine learning and mathematical engineering problems and methods (including also optimization, system identification, computational statistics, signal processing, data visualization, deep learning, compressed sensing and big-data). The emphasis is especially on open-source implementations in high-level programming languages, including but not limited to Julia, Python, Scala and R. For further information see the workshop homepage.
The 3 days main event (8-10 September) will consist of invited and contributed talks as well as poster presentations. It will be followed by a 2 days additional event (11-12 September) including software demos and hands-on tutorials on selected topics. 
Attendees can register to the main event only or to the full workshop. Submission of extended abstracts are solicited for the main event. Submission of demo presentations are solicited for the two days additional event. For further information (including Registration, Location and Venue) see details at the workshop website.
Important dates: 
Deadline extended abstract/demo submission: 31 July 2014
Deadline for registration: 1 September 2014
Confirmed invited speakers (talks and tutorials): 
James Bergstra, Center for Theoretical Neuroscience, University of Waterloo:
Theano and Hyperopt: Modelling, Training, and Hyperparameter Optimization in Python
Jeff Bezanson, MIT:
TBA
Luis Pedro Coelho, European Molecular Biology Laboratory (EMBL):
Large Scale Analysis of Bioimages Using Python
Steven Diamond, Stanford University
Convex Optimization in Python with CVXPY
Stefan Karpinski, MIT
TBA
Graham Taylor, School of Engineering, University of Guelph:
An Overview of Deep Learning and Its Challenges for Technical Computing
Ewout van den Berg, IBM T.J. Watson Research Center:
Tools and Techniques for Sparse Optimization and Beyond
Organizing committee: 
Marco Signoretto, Department of Electrical Engineering, KU Leuven
Johan Suykens, Department of Electrical Engineering, KU Leuven
Vilen Jumutc , Department of Electrical Engineering, KU Leuven
For further information (including Registration, Location and Venue) see http://www.esat.kuleuven.be/stadius/tcmm2014/


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.

Fast matrix completion without the condition number - implementation -


Fast matrix completion without the condition number by Moritz Hardt, Mary Wootters

We give the first algorithm for Matrix Completion whose running time and sample complexity is polynomial in the rank of the unknown target matrix, linear in the dimension of the matrix, and logarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix in the running time. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.

The attendant implementation is on Mary Wootters research page.

You can also watch a video of Mary at COLT:  Fast Matrix Completion Without the Condition Number, Mary Wootters






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, July 24, 2014

The 200 Million Dollar Assumption

There used to be the Six Million Dollar Man, but now with inflation and all, we have the 200 Million Dollar Assumption. In some of the Slides from the workshop on Science on the Sphere, you may have noticed this slide from Tom Kitching on Weak lensing on the sphere



I went ahead and asked Tom what he meant by mentioning a 200M$ assumption, here is what he responded:

Dear Igor,

Thank you for your email.

The the plot on the slide is from this paper http://arxiv.org/pdf/1007.2953.pdf where we investigated the impact of the "Limber approximation" on weak lensing statistics and forecasted cosmological parameter error. The approximation replaces Bessel functions with delta functions to make calculations easier, and should be ok for small scales (where the functional approximation is asymptotically ok). What we found was that the predicted marginalised 1-sigma error bars using the Limber approximation are about 20% larger than when the approximation is not used.

Future experiments such as Euclid, LSST and SKA are to cost about 1 billion euros/dollars so a 20% increase in error bars on the key parameters is the equivalent cost of nearly 200M.

This was a slightly provocative statement aimed to stimulate discussion on how we can avoid this and other approximations to fully exploit these new experiments. In fact it reminds me of a sporting analogy where it is often said that the "aggregated effect of marginal gains" (e.g. http://www.bbc.co.uk/sport/0/olympics/19174302) can result in wins; where small differences can all add up to a significant difference.

I hope that helps, let me know if you have any further questions.

Best Regards
Tom
Thanks Tom !

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.

Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed $\ell_1/ell_2$ Regularization

Laurent Duval just sent me the following:

Dear Igor
Nuit Blanche is a nest of choice for many sparsities. The ones of concern here are those approximated by an $l_1/l_2$, or Taxicab/Euclidean norm ratio, which was already covered in some of your posts: 
We propose in the following preprint a smoothed, parametrized penalty, termed SOOT for "Smoothed-One-Over-Two" norm ratio, with results on its theoretical convergence, and an algorithm based on proximal methods. It is applied to blind deconvolution, here for seismic data. We hope it could be of interest to your readership. 
[Abstract]
The $\ell_1/ell_2$ ratio regularization function has shown good performance for retrieving sparse signals in a number of recent works, in the context of blind deconvolution. Indeed, it benefits from a scale invariance property much desirable in the blind context.
However, the $\ell_1/ell_2$ function raises some difficulties when solving the nonconvex and nonsmooth minimization problems resulting from the use of such regularization penalties in current restoration methods.
In this paper, we propose a new penalty based on a smooth approximation to the $\ell_1/ell_2$ function. In addition, we develop a proximal-based algorithm to solve variational problems involving this function and we derive theoretical convergence results. We demonstrate the effectiveness of our method through a comparison with a recent alternating optimization strategy dealing with the exact $\ell_1/ell_2$ term, on an application to seismic data blind deconvolution.

[arXiv Link]
Amitiés
Laurent

******** Travail et autres activités/Work and misc. ********

Thanks Laurent !

From the paper: "The code will be made available at http://www-syscom.univ-mlv.fr/ upon the paper acceptance"

All the blind deconvolution blog entries are at: 


Wednesday, July 23, 2014

Slides: Summer School on Hashing: Theory and Applications, 2014



The webpage of the EADS Summer School on Hashing: Theory and Applications that took place on July 14-17, 2014 at University of Copenhagen, Denmark, now features the slides of the presentation made there:


OVERVIEW AND GOAL

Hashing is used everywhere in computing and is getting increasingly important with the exploding amount of data. The summer school will provide an in-depth introduction to hashing, both theory and applications. The topics range will from modern theory of hashing, to actual implementations of hash functions that are both efficient and provide the necessary probabilistic guarantees. Application areas will be studied, from sketching and data bases, to similarity estimation, and machine learning.


Rasmus Pagh Dictionaries with implicit keys (July 15) Michael Mitzenmacher
Bloom Filters and Such (July 14)
Cuckoo hashing and balanced allocations (July 15)
Mikkel Thorup
High speed hashing for integers and strings (July 14)
Reliable hashing for complex applications (July 15)
Graham Cormode

Complexity-Matching Universal Signal Estimation in Compressed Sensing



In light to a recent update on ArXiv, I asked Dror Baron to provide me some context on his different papers related to universal signal recovery, here is what he had to say: 

Hello Igor,

Here's a link to a recent submission: http://arxiv.org/abs/1204.2611
I know that we have multiple related algorithms recently, so let me try to explain:

1. In a compressed sensing problem, y=A*x+z, this work is trying to solve xhat = argmin_w H(w)-log(f_Z(zhat=y-A*w)), where xhat is our estimate for x given y and A, w is a hypothesized solution, H(.) is entropy (in our case empirical entropy, which serves as a sort of universal coding length), and f_Z(.) is the density function for the noise. This algorithm seems to approach the minimum mean square error (MMSE) up to 3 dB or so, which is theoretically motivated. Our optimization algorithm relies on Markov chain Monte Carlo (MCMC).

2. In our paper from last week, we used a universal denoiser within approximate message passing. We hope that with some bells and whistles the algorithm might consistently outperform MCMC by that 3 dB gap.

Please feel free to let us know if you have any questions!

Dror
--
Dror Baron, Ph.D.
Assistant Professor
Electrical and Computer Engineering Department
North Carolina State University


We study the compressed sensing (CS) signal estimation problem where an input signal is measured via a linear matrix multiplication under additive noise. While this setup usually assumes sparsity or compressibility in the input signal during recovery, the signal structure that can be leveraged is often not known a priori. In this paper, we consider universal CS recovery, where the statistics of a stationary ergodic signal source are estimated simultaneously with the signal itself. Inspired by Kolmogorov complexity and minimum description length, we focus on a maximum a posteriori (MAP) estimation framework that leverages universal priors to match the complexity of the source. Our framework can also be applied to general linear inverse problems where more measurements than in CS might be needed. We provide theoretical results that support the algorithmic feasibility of universal MAP estimation using a Markov chain Monte Carlo implementation, which is computationally challenging. We incorporate some techniques to accelerate the algorithm while providing comparable and in many cases better reconstruction quality than existing algorithms. Experimental results show the promise of universality in CS, particularly for low-complexity sources that do not exhibit standard sparsity or compressibility.


Tuesday, July 22, 2014

Context Aware Recommendation Systems ( Lei Tang, Xavier Amatriain)



Much like the presentation by Lei Tang (Wallmart Labs) on Adaptive User Segmentation for Recommendation at last year's GraphLab 2013 (see Slides (pdf) here and video here). Xavier Amatriain, of Netflix, made a presentation of what we should be expecting in terms of recommendation. The idea here is that most of this work cannot be static otherwise your customers just won't be responsive to it. Here are his slides and the attendant videos from the Machine Learning Summer School organized in Pittsburgh 2014 by Alex Smola. I note the focus put on matrix and tensor factorizations and the persistent reference to blog posts. It's a new world...more on that later.

Dynamic MR image reconstruction–separation from undersampled (k,t)-space via low-rank plus sparse prior - implementation -



Benjamin Trémoulhéac just sent me the following:

Dear Igor,

You and your readers might be interested in my paper recently published (early view) which is about the use of the RPCA (or L+S) model in dynamic MR imaging from partial Fourier samples for both reconstruction and separation:
Dynamic MR image reconstruction–separation from undersampled (k,t)-space via low-rank plus sparse prior
(This is an open access article thanks to the new policy in the UK)
I have made available an implementation of the algorithm in matlab here
Note that interestingly Otazo et al. have published almost simultaneously a very similar work in a different journal:

Otazo et al, Low-rank plus sparse matrix decomposition for accelerated dynamic MRI with separation of background and dynamic components, 2014
Yet there are some differences, so these papers are kind of complementary.

Thanks!
Best regards,
Benjamin Trémoulhéac
Thank you Benjamin. Here is the paper:



Dynamic magnetic resonance imaging (MRI) is used in multiple clinical applications, but can still benefit from higher spatial or temporal resolution. A dynamic MR image reconstruction method from partial (k-t)-space measurements is introduced that recovers and inherently separates the information in the dynamic scene. The reconstruction model is based on a low-rank plus sparse decomposition prior, which is related to robust principal component analysis. An algorithm is proposed to solve the convex optimization problem based on an alternating direction method of multipliers. The method is validated with numerical phantom simulations and cardiac MRI data against state of the art dynamic MRI reconstruction methods. Results suggest that using the proposed approach as a means of regularizing the inverse problem remains competitive with state of the art reconstruction techniques. Additionally, the decomposition induced by the reconstruction is shown to help in the context of motion estimation in dynamic contrast enhanced MRI.


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.

Tensor Networks for Big Data Analytics and Large-Scale Optimization Problems

Interesting review of the TT approach:





In this paper we review basic and emerging models and associated algorithms for large-scale tensor networks, especially Tensor Train (TT) decompositions using novel mathematical and graphical representations. We discus the concept of tensorization (i.e., creating very high-order tensors from lower-order original data) and super compression of data achieved via quantized tensor train (QTT) networks. %The purpose of a tensorization and quantization is to achieve, via low-rank tensor approximations %"super" compression, and meaningful, compact representation of structured data. The main objective of this paper is to show how tensor networks can be used to solve a wide class of big data optimization problems (that are far from tractable by classical numerical methods) by applying tensorization and performing all operations using relatively small size matrices and tensors and applying iteratively optimized and approximative tensor contractions.


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.