Slides: IPAM Deep Learning, Feature Learning Graduate Summer School

Here is the program and the slides of the Deep Learning, Feature Learning Graduate Summer School that took place at IPAM, July 9 - 27, 2012

Monday, July 09, 2012
Morning Session
8:00 - 8:45	Check-In/Breakfast (Hosted by IPAM)
8:45 - 9:00	Welcome and Opening Remarks
9:00 - 10:00	Geoffrey Hinton (University of Toronto) "PART 1: Introduction to Deep Learning & Deep Belief Nets (PDF Parts 1 & 2)"  Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Geoffrey Hinton (University of Toronto) "PART 2: Using backpropagation for fine-tuning a generative model to be better at discrimination"
11:30 - 12:00	Break
12:00 - 1:00	Joint talk: James Bergstra (Harvard), Clement Farabet (NYU)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Yann LeCun (New York University) "Deep Learning, Graphical Models, EnergyBased Models, Structured Prediction" Presentation (PDF File)
3:30 - 4:00	Break
4:00 - 5:00	Yann LeCun (New York University) "Deep Learning, Graphical Models, EnergyBased Models, Structured Prediction" Presentation (PDF File)
5:00 - 6:30	Reception (Hosted by IPAM)
Tuesday, July 10, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Andrew Ng (Stanford University) "Deep Learning, Self-Taught Learning and Unsupervised Feature Learning (Part 1 Slides1-68; Part 2 Slides 69-109)" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Andrew Ng (Stanford University) "Advanced topics + Research philosophy / Neural Networks: Representation" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Andrew Ng (Stanford University) "Non-linear hypotheses"
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Andrew Ng (Stanford University) "Non-linear hypotheses"
3:30 - 4:00	Break
4:00 - 5:00	Joint talk: James Bergstra (Harvard), Clement Farabet (NYU)
Wednesday, July 11, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Yann LeCun (New York University) "Learning Hierarchies of Invariant Features (Parts 1 & 2)" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Yann LeCun (New York University) "Deep Learning, Graphical Models, EnergyBased Models, Structured Prediction" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Joint talk: James Bergstra (Harvard), Clement Farabet (NYU)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Geoffrey Hinton (University of Toronto) "PART 3: Some applications of deep learning (Slides 1-38)" Presentation (PDF File)
3:30 - 4:00	Break
4:00 - 5:00	Geoffrey Hinton (University of Toronto) "PART 4: A computational principle that explains sex, the brain, and sparse coding (Slides 39-92)" Presentation (PDF File)
Thursday, July 12, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Rob Fergus (New York University) "Deep Learning Methods for Vision" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Rob Fergus (New York University) "Deep Learning Methods for Vision" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Geoffrey Hinton (University of Toronto) Presentation (PDF File)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Alan Yuille (University of California, Los Angeles (UCLA))
3:30 - 4:00	Break
4:00 - 5:00	Joint talk: James Bergstra (Harvard), Clement Farabet (NYU)
Friday, July 13, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Graham Taylor (University of Guelph) Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Graham Taylor (University of Guelph) Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Alan Yuille (University of California, Los Angeles (UCLA))
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Alan Yuille (University of California, Los Angeles (UCLA))
3:30 - 4:00	Break
4:00 - 5:00	Yann LeCun (New York University) "Deep Learning, Graphical Models, EnergyBased Models, Structured Prediction" Presentation (PDF File)
Monday, July 16, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Yoshua Bengio (University of Montreal)
10:00 - 10:30	Break
10:30 - 11:30	Yoshua Bengio (University of Montreal)
11:30 - 12:00	Break
12:00 - 1:00	Stephen Wright (University of Wisconsin-Madison) "Some Relevant Topics in Optimization (Part 1) - (Slides Cover Parts 1 & 2)" Presentation (PDF File)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Stephen Wright (University of Wisconsin-Madison) "Some Relevant Topics in Optimization (Part 2)"
3:30 - 4:00	Break
4:00 - 5:00	Arthur Szlam (New York University) "A tutorial on sparse modeling." Presentation (PDF File)
5:00 - 6:30	Reception (Hosted by IPAM)
Tuesday, July 17, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Stephen Wright (University of Wisconsin-Madison) "Sparse and Regularized Optimization Part 1 (Slides Cover Parts 1 & 2)" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Stephen Wright (University of Wisconsin-Madison) "Sparse and Regularized Optimization Part 2" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Arthur Szlam (New York University)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Yoshua Bengio (University of Montreal)
3:30 - 4:00	Break
4:00 - 5:00	Yoshua Bengio (University of Montreal)
Wednesday, July 18, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Stéphane Mallat (École Polytechnique) "Scattering Invariant Deep Networks for Classification " Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Stéphane Mallat (École Polytechnique) "Scattering Invariant Deep Networks for Classification " Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Kai Yu (Baidu Inc.)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Kai Yu (Baidu Inc.)
3:30 - 4:00	Break
4:00 - 5:00	Jorge Nocedal (Northwestern University) "Tutorial on Optimization methods for machine learning" Presentation (PDF File)
Thursday, July 19, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Jorge Nocedal (Northwestern University) "Tutorial on Optimization methods for machine learning" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Jorge Nocedal (Northwestern University)
11:30 - 2:00	Lunch (on your own)
Afternoon Session
2:00 - 3:30	Stéphane Mallat (École Polytechnique)
3:30 - 4:00	Break
4:00 - 5:00	Jason Morton (Pennsylvania State University) "An Algebraic Perspective on Deep Learning" Presentation (PDF File)
Friday, July 20, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Jason Morton (Pennsylvania State University) "An Algebraic Perspective on Deep Learning" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Jason Morton (Pennsylvania State University) "An Algebraic Perspective on Deep Learning" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Yoshua Bengio (University of Montreal)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Stanley Osher (University of California, Los Angeles (UCLA))
3:30 - 4:00	Break
4:00 - 5:00	Stanley Osher (University of California, Los Angeles (UCLA))
Monday, July 23, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Ruslan Salakhutdinov (University of Toronto) Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Ruslan Salakhutdinov (University of Toronto) Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Marc'Aurelio Ranzato (Google Inc.) "Deep Gated MRF's - part 1" Presentation (PDF File)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Marc'Aurelio Ranzato (Google Inc.) "Deep Gated MRF's - part 2" Presentation (PDF File)
3:30 - 4:00	Break
4:00 - 5:00	Jason Weston (Google Research)
5:00 - 6:30	Reception (Hosted by IPAM)
6:30 - 7:30	Brian Milch (Google Inc.) "From Text to Concepts at Google"
Tuesday, July 24, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Jason Weston (Google Research)
10:00 - 10:30	Break
10:30 - 11:30	Jason Weston (Google Research)
11:30 - 12:00	Break
12:00 - 1:00	Ruslan Salakhutdinov (University of Toronto) Presentation (PDF File)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Bruno Olshausen (University of California, Berkeley (UC Berkeley)) "From natural scene statistics to models of neural coding and representation (part 1)" Presentation (PDF File)
3:30 - 4:00	Break
4:00 - 5:00	Marc'Aurelio Ranzato (Google Inc.) "Large Scale Deep Learning" Presentation (PDF File)
Wednesday, July 25, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Thomas Serre (Brown University) "Deep learning in the visual cortex - Part 1" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Thomas Serre (Brown University) "Deep learning in the visual cortex - Part 2" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Roland Memisevic (Johann Wolfgang Goethe-Universität Frankfurt) "Multiview Feature Learning - Part 1" Presentation (PDF File)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Roland Memisevic (Johann Wolfgang Goethe-Universität Frankfurt) "Multiview Feature Learning - Part 2" Presentation (PDF File)
3:30 - 4:00	Break
4:00 - 5:00	Bruno Olshausen (University of California, Berkeley (UC Berkeley)) "From natural scene statistics to models of neural coding and representation (part 2)" Presentation (PDF File)
Thursday, July 26, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Iain Murray (University of Edinburgh) "Introduction to MCMC for deep learning" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Iain Murray (University of Edinburgh) "Density estimation" Presentation (PDF File)
11:30 - 12:00	Break
12:00 - 1:00	Nando de Freitas (University of British Columbia)
1:00 - 2:30	Lunch (on your own)
Afternoon Session
2:30 - 3:30	Nando de Freitas (University of British Columbia)
3:30 - 4:00	Break
4:00 - 5:00	Thomas Serre (Brown University) "Deep learning in the visual cortex - Part 3" Presentation (PDF File)
Friday, July 27, 2012
Morning Session
8:00 - 9:00	Continental Breakfast
9:00 - 10:00	Nando de Freitas (University of British Columbia) "An Informal Mathematical Tour of Feature Learning" Presentation (PDF File)
10:00 - 10:30	Break
10:30 - 11:30	Nando de Freitas (University of British Columbia)

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.

We live in exciting times !

You probably recall last week's entries on

• Intra-Block Correlation and Sparse Sensing Matrices
• More intra-block correlation and sparse sensing matrices

Go read them I'll wait. Zhilin sent me the following:

Dear Igor, 

I read your post "  More intra-block correlation and sparse sensing matrices " which presents Phil's email. After he introduced his several nice papers, in the end of the email Phil said "we get performance that meets or exceeds that of Bayesian or variational techniques, but with orders-of-magnitude reduction in complexity". I believe Phil was saying that AMP algorithms meet or exceed the performance of Bayesian or variational techniques in the scenarios/applications given in their papers.

There are several scenarios where SBL has obvious advantages over other algorithms. One situation is when the sensing matrix is coherent (i.e., columns are largely correlated). This situation is often encountered in source localization and tracking (e.g. direction-of-arrival estimation, brain source localization, radar detection), biomedical data analysis (e.g. neuroimaging data pattern recognition), and computer vision (e.g. face/expression recognition). SBL algorithms generally have much better performance than other algorithms in these applications. David Wipf also has a NIPS 2011 paper, titled : "Sparse Estimation with Structured Dictionaries", which mathematically proved why SBL is better than Lasso in this situation (Note that the so-called dictionary matrix in this paper is indeed the sensing matrix in a standard CS experiment. I hope readers won't be confused by these names).

There is a source localization demo using a sensing matrix from real-world data, which can be downloaded at: http://dsp.ucsd.edu/~zhilin/papers/Localization.zip. In this demo I compared three MMV algorithms developed in our lab. Anyone can use his/her favorite algorithm in this demo to see the performance.

When signals are structured but non-sparse or less-sparse, SBL algorithms also have good performance, as shown in my wireless telemonitoring paper, " Low Energy Wireless Body-Area Networks for Fetal ECG Telemonitoring via the Framework of Block Sparse Bayesian Learning". Also, my BSBL paper, titled " Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation", shows that in a noise-free situation, after exploiting block structure and intra-block correlation, BSBL algorithms can exactly recover sparse signals with K non-zero elements from only K measurements with high success rates (>0.99). Thus, SBL is helpful in the applications when signals are not very sparse.

SBL algorithms are often criticized for slow speed. But I think the situation will change. One reason is that SBL algorithms can be transformed into iterative reweighted algorithms. For example, in the above BSBL paper, BSBL-L1 can be implemented by iteratively running group Lasso 3-4 times or less. Since every year there are a number of more efficient Lasso-type algorithms proposed, it is expected that BSBL-L1 can be faster and faster. Another reason is there are several methods to speed up SBL algorithms, such as bounded-optimization technique used in my BSBL-BO algorithm, and the fixed-point method, which was used in my CVPR 2012 paper, titled "Sparse Bayesian Multi-Task Learning for Predicting Cognitive Outcomes from Neuroimaging Measures in Alzheimer's Disease". And we also have several much faster algorithms and will be submitted soon.

In the end, I want to say it is hard to say AMP outperforms SBL, or SBL outperforms AMP. AMP and SBL, as two benchmarks, have advantages in different applications/scenarios. We all enjoy seeing both AMP and SBL are evolving for [the] better.

Best,

Zhilin

[ for reference: Zhilin's SBL solver is here. Phil Schinter's DCS-AMP solver is here. ]

Thanks  Zhilin. I am pretty sure the attentive reader drew similar conclusions. But I think eventually this type of exchange shows that there is something at play here. Whether or not we have the choice for the measurement matrix is indeed an issue. To me, the other issue is really trying to figure out why some of these results stand: Is this due to the choice of the measurement matrix ? or a constraint on the unknown vector such as sparsity? or because of a specific distribution for that vector ? or even some deeper knowledge of the structure of that vector ? I can safely say that this is an exciting time as I don't think we have a clear view of these subjects and boundaries. 

My other take away from this debate is that it is all the more important for the theoretically minded to jump in. Indeed, it would be nice for the hardware makers to get a feedback from the theoretical folks on how much they should care on the structure of the measurement matrix and derive some new hardware or if some sorts of insightful knowledge will make the detail of the hardware somewhat irrelevant.

As it turns out Larry Wasserman just wrote the following entry on his blog:  RIP RIP (Restricted Isometry Property, Rest In Peace), and I think there is a parallel. Go read it I'll wait.....In his indictment of RIP for regression purposes, he also writes:

Compressed sensing is different. In these applications, the regression  refers to data coming from some device. We actually design and build the device in such a way that the linear assumption is true. Moreover, part if the device design is that we get to make up the ‘s (not nature). In particular, we can choose the design matrix. Thus, we can force the RIP to hold. In this engineering applications, linearity and RIP are not just convenient mathematical assumptions. They are design features. They are real.

I then commented on his blog:

Larry, 

Within Compressed Sensing, RIP is not a condition for sparse recovery that is in fashion anymore. In particular since about 2008 and the work of Donoho and Tanner [1], we have empirical proofs that in general this condition is too stringent. The generic Donoho-Tanner phase transition generally shows that l_1 recovery of sparse vectors admit less sparse vectors than what RIP would require.

In a certain sense, the “coup de grace” was given to that argument recently with a phase transition even beyond the traditional Donoho-Tanner PT (see [2]) and initially featured in the work of Krzakala et al [3]. All this can be easily pictured in this beautiful hand crafted drawing I made for the occasion: http://goo.gl/H3m4C 

The work of Krzakala et al [3] show that by choosing the right design matrix, one can attain very interesting limits. Right, within the community, there is an on-going discussion as to whether we ought to put some constraint on the design matrix or push further the constraint on the vector to be recovered. On the one hand, it means, we need to design different hardware, on the other, it means we need to dig further in the structured sparsity world that the ML folks are investigating. An example of that discussion can be found in [4] and [5].

But let me play the devil’s advocate for RIP, at least within compressive sensing. RIP was for a long while the only mathematically rigorous reasoning at hand for people to show that their empirical finding held even if in most of these papers, the authors acknowledged that their design matrices did not fit the RIP condition. To a certain extent, I can bet you could not even get a paper out unless the first few paragraphs talked about the solid reason as to why sparse recovery was possible (thanks to RIP). We have also seen many authors coming up with different conditions paralleling RIP, so it was a useful tool for a while.

There is also another aspect as to why RIP is interesting: It is a similar tool that is currently used to investigate low rank type of algorithms. Here again, I am sure that most phase transition discovered there will show that RIP is too stringent, but again it may be the only theoretical tool around grounded in some theory.

Cheers,

Igor.

[1] Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing by Jared Tanner and David L. Donoho http://www.maths.ed.ac.uk/~tanner/DoTa_Universality.pdf 

[2] Compressive Sensing: The Big Picture, https://sites.google.com/site/igorcarron2/cs#measurement 

[3] Statistical physics-based reconstruction in compressed sensing by Florent Krzakala, Marc Mézard, François Sausset, Yifan Sun, Lenka Zdeborová, http://arxiv.org/abs/1109.4424 

[4] http://nuit-blanche.blogspot.com/2012/08/intra-block-correlation-and-sparse.html[5] http://nuit-blanche.blogspot.com/2012/08/more-intra-block-correlation-and-sparse.html

Because here again, this new phase transition can be attained through the construction of dedicated matrices ( Krzakala et al ) or by choosing a specific type of distributions as shown by Phil Schniter. Here again we are torn between the simple hardware question: should I design a hardware / sensor around a special set of  "magic matrices" or should I strive for a representation of the signal so that it has a certain distribution (like Bernouilli)

To which Larry kindly replied with:

Thanks for the comment Igor.

Perhaps I focused too much on RIP. My real point was that ANY conditions needed for recovery are unrealistic for vanilla regression problems. To put it another way, recovery is (usually) not an interesting problem in ordinary regression. (As a pedantic example, take two covariates to be perfectly correlated. You can’t separate the two but you don’t need to if you focus on predictive accuracy.) In other words, regression and compressed sensing are very different problems (despite the obvious overlap). But the difference often gets ignored in some statistics papers.

Thanks for the discussion and references

Larry

I could see some problem in blind deconvolution where the problematic might overlap in a more meaningful way but this is a good point from the regression standpoint. 

To come back to compressive sensing and the current not-so-well understood relationship between measurement matrices, structured sparsity and solvers, much like Curiosity on the surface of Mars, we live  in exciting times.

Photo: NASA/JPL/Caltech

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.

Direct Optimization of the Dictionary Learning Problem - implementation -

While the Direct optimization of the dictionary learning problem Toolbox is here, the paper featuring the technique is here: Direct Optimization of the Dictionary Learning Problem by Alain Rakotomamonjy, The abstract reads:

A novel way of solving the dictionary learning problem is proposed in this paper. It is based on a so-called direct optimization as it avoids the usual technique which consists in alternatively optimizing the coefficients of a sparse decomposition and in optimizing dictionary atoms. The algorithm we advocate simply performs a joint proximal gradient descent step over the dictionary atoms and the coefficient matrix. As such, we have denoted the algorithm as a one-step block-coordinate proximal gradient descent and we have shown that it can be applied to a broader class of non-convex optimization problems than the dictionary learning one. After having derived the algorithm, we also provided in-depth discussions on how the stepsizes of the proximal gradient descent have been chosen. In addition, we uncover the connection between our direct approach and the alternating optimization method for dictionary learning. The main advantage of our novel algorithm is that, as suggested by our simulation study, it is far more efficient than alternating optimization algorithms.

Image Credit: NASA/JPL-Caltech. This image was taken by Rear Hazcam: Right A (RHAZ_RIGHT_A) onboard NASA's Mars rover Curiosity on Sol 0 (2012-08-06 06:03:27 UTC) . 
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.

Compressive Sensing related PostDoc at Sandia

Remember Jovana Ilic in Does Richter's "4096 Colours" painting fulfill the Restricted Isometry Property for Sparse Signal Recovery ?, well she just sent me the following announcement for a postdoc position (all other jobs are posted at http://nuit-blanche.blogspot.com/search/label/CSjobs ). Here it is:

Hi Igor, 

My mentor at Sandia, Tammy Kolda (http://csmr.ca.sandia.gov/~tgkolda/) has a postdoc position for a project that involves compressed sensing. I was wondering if you could possibly advertise it on your blog? Below is the brief description of the position: 

We have multiple openings for postdoctoral researchers in computer science, computer engineering, mathematics, and statistics. We are particularly looking for experts in informatics and data sciences, numerical mathematics (especially linear algebra), network and graph algorithms, and cyber defense. The successful applicant will be expected to conduct innovative research, to develop open-source software, to present his or her findings at leading conferences and workshops, and to publish his or her results in leading journals. This postdoctoral position is for motivated and enthusiastic individuals with a background in computer science, mathematics, statistics, or related areas.and the full job posting can be found here: 

https://ws03snlntz.sandia.gov/psp/applicant/EMPLOYEE/HRMS/c/HRS_HRAM.HRS_CE.GBL?Page=HRS_CE_JOB_DTL&Action=A&JobOpeningId=641145&SiteId=1&PostingSeq=1

For more information, please contact Tammy Kolda: :tgkolda@sandia.gov

Thanks,

Jovana

Credit: NASA/JPL/University of Arizona  The Descent of Mars Curiosity during the 7 minutes of Terror as photographed from the HiRise camera

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.

Applying alternating direction method of multipliers for constrained dictionary learning -implementation-

The ADMM for dictionary learning Toolbox is here while the paper featuring the technique is: Applying alternating direction method of multipliers forconstrained dictionary learning, by Alain Rakotomamonjy, The abstract reads:

This paper revisits the problem of dictionary learning that we address through a numerical scheme that optimizes alternatively the dictionary elements and the coe cient matrix. Our rst contribution consists then in providing a simple proof of convergence of this scheme for a large class of constraints and regularizers on the dictionary atoms. Then, we investigates the use of a well-known optimization method named alternating direction method of multipliers for solving each of the alternate step of the dictionary learning problem. We show that such an algorithm yields to several bene ts. Indeed, it can be more e cient than other competing algorithms such as Iterative Shrinkage Thresholding approach and besides, it allows one to easily deal with mixed constraints or regularizers over the dictionary atoms or approximation coeffi cients. For instance, we have induced joint sparsity, positivity and smoothness of dictionary atoms by means of total variation and sparsity-inducing regularizers. Our experimental results prove that using these mixed constraints helps in achieving better learned dictionary especially when learning from noisy signals.

Image Credit: NASA/JPL-Caltech,  This image was taken by Front Hazcam: Right A (FHAZ_RIGHT_A) onboard NASA's Mars rover Curiosity on Sol 0 (2012-08-06 05:20:36 UTC) .

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.

WSPGL1: Beyond L1 minimization for sparse signal recovery - implementation -

Hassan Mansour just sent me the following:

Dear Igor, 

I would like to point out that we have released the code for the WSPGL1 algorithm which I will be presenting tomorrow at the SSP 2012 workshop on Ann Arbor, MI.

The attendant paper and code are available for download from: 

http://www.cs.ubc.ca/~hassanm/WSPGL1_code.htm 

The algorithm performs an embedded re-weighting inside the subroutines of the SPGL1 algorithm updating the Pareto curve with every reweighted subproblem. The result is an improved sparse recovery performance compared with standard L1 minimization with no additional computational cost. 

Thanks for spreading the word. 

Cheers,

-Hassan-

The paper explaining the algorithm is:Beyond L1 minimization for sparse signal recovery by  Hassan Mansour.. The abstract reads:

Sparse signal recovery has been dominated by the basis pursuit denoise (BPDN) problem formulation for over a decade. In this paper, we propose an algorithm that outperforms BPDN in finding sparse solutions to underdetermined linear systems of equations at no additional computational cost. Our algorithm, called WSPGL1, is a modification of the spectral projected gradient for `1 minimization (SPGL1) algorithm in which the sequence of LASSO subproblems are replaced by a sequence of weighted LASSO subproblems with constant weights applied to a support estimate. The support estimate is derived from the data and is updated at every iteration. The algorithm also modifies the Pareto curve at every iteration to reflect the new weighted `1 minimization problem that is being solved. We demonstrate through extensive simulations that the sparse recovery performance of our algorithm is superior to that of `1 minimization and approaches the recovery performance of iterative re-weighted `1 (IRWL1) minimization of Candes, Wakin, and Boyd, although it does not match ` it in general. Moreover, our algorithm has the computational cost of a single BPDN problem.

Thanks Hassan !

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.

Postdoc: Application of Sparse Representation Theory to the Adaptive Control of Robot Arms

Other Jobs announcement can be found by searching for the CSJobs tag:

http://nuit-blanche.blogspot.com/search/label/CSjobs 

or in the jobs section of the Compressive Sensing Group Jobs listing.

In the meantime, Glen Henshaw sent me the following:

Hi Igor,

I'm looking for a postdoc - was hoping you could advertise it on Nuit Blanche. It's a 2-year position in the Space Robotics Lab of the Naval Center for Space Technology, which is part of the Naval Research Laboratory in Washington DC. I'm looking for someone to help research the application of sparse representations to the adaptive control of robotic manipulators. 

   The position is to perform research into the application of sparse representation theory to the adaptive control of robot arms. The applicant must have a research background in compressive sensing, sparse approximation theory, and/or L1 norm optimization; knowledge of robotic kinematics, dynamics, and control is not absolutely required but is a big plus. The (recently awarded)  PhD should be in mathematics, statistics, applied mathematics, or possibly computer science or engineering, but in the latter case he/she must have a strong mathematics background that is clear from the CV. The applicant should also have a background in scientific computing, preferably with some experience in writing parallel MIMD or CUDA numerical code.

   The position is only open to US citizens and permanent residents. Applicants should identify in their first email whether they are US citizens or permanent residents, and if the latter, their country of citizenship. CVs can be forwarded to glen.henshaw@nrl.navy.mil.

Thanks Glen. 

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.

Dynamic Compressed Sensing (DCS) via Approximate Message Passing (AMP) - implementation -

From Phil Schniter's email in More intra-block correlation and sparse sensing matrices we have an implementation of the AMP algoriithm for Dynamic Compressed Sesning:  The DCS-AMP homepage is here. The introduction reads:

Dynamic Compressed Sensing (DCS) | Approximate Message Passing (AMP)

DCS-AMP is a recently developed Bayesian algorithm for solving the dynamic compressed sensing (DCS) problem in compressed sensing, in cases with (possibly) substantial amplitude correlation across time. The technique leverages recent advances in approximate message passing (AMP) in order to rapidly obtain accurate solutions in high-dimensional settings.

As a reminder the supporting paper is: Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing by  Justin Ziniel  and Philip Schniter. The abstract reads:

In this work the dynamic compressive sensing (CS) problem of recovering sparse, correlated, time varying signals from sub-Nyquist, non-adaptive, linear measurements is explored from a Bayesian perspective. While there has been a handful of previously proposed Bayesian dynamic CS algorithms in the literature, the ability to perform inference on high-dimensional problems in a computationally efficient manner remains elusive. In response, we propose a probabilistic dynamic CS signal model that captures both amplitude and support correlation structure, and describe an approximate message passing algorithm that performs soft signal estimation and support detection with a computational complexity that is linear in all problem dimensions. The algorithm, DCS-AMP, can perform either causal filtering or non-causal smoothing, and is capable of learning model parameters adaptively from the data through an expectation maximization learning procedure. We provide numerical evidence that DCS-AMP performs within 3 dB of oracle bounds on synthetic data under a variety of operating conditions. We further describe the result of applying DCS-AMP to two real dynamic CS datasets, as well as a frequency estimation task, to bolster our claim that DCS-AMP is capable of offering state-of-the-art performance and speed on real-world high-dimensional problems.

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.

The high stakes of Curiosity's Entry, Descent, and Landing (EDL)

And so it begins, Curiosity is entering Mars' atmosphere at 13,000 mph. We'll know when it has properly landed in about 16 minutes, 7 minutes for the actual entry and landing (EDL) and about 9 minutes for the signal to get back to Earth. 

Well, while we are waiting for these very long seven minutes + signal time, I added the price tag for Curiosity (the MSL mission) 2.5B$ against the complexity index featured in this Cost of Success or Failure versus Complexity in Space Voyages graph. mentioned in a  recent National Academies of Science report.

What is the estimated complexity index of Curiosity, I don't know so I cannot figure out which of these mission is MSL. However, this is what I found on a cursory look from Why is Mars so hard? a 2003 article:

The Aerospace Corporation study assigned each mission a “Complexity Index” score between 0 and 1: 0 for the least-complex mission in the study group and 1 for the most complex. MER received a Complexity Index score of 0.81, putting it the same category of missions as NASA’s flagship outer planetary missions Galileo and Cassini.

MER are the two smaller rovers already on Mars (Opportunity and Spirit). It would seem that Curiosity is a little more complex especially considering it is bigger and because of its delicate landing procedure for which the outcome we are all waiting for. 

However, at the same time, it uses some of the technology already used in MER and it is also simpler than MER because it uses plutonium-238 for its RTGs and therefore does not have to rely on solar panels for power. In short, it very likely that Curiosity is above the regression line at lower complexity than 80% which puts it in a sweet spot.

This entry, descent, and landing (EDL) success of Curiosity will prove itself to be of importance not just for Curiosity but also for future rovers such as MAX-C: From the NAP report:(page 271):

A final point regarding MAX-C is that its success depends in part on the success of the MSL EDL system. If that system functions properly in 2012, then a $2.5 billion MAX-C mission should go forward for launch in 2018. If it fails, however, then NASA will have to reconsider the priority and schedule for MAX-C. If the cause of failure can be determined and appropriate and affordable changes can be made in time to preserve a 2018 launch, then MAX-C can continue on schedule. But if uncertainties remain or if the necessary changes cannot be made by 2018, then MAX-C should slip in priority and schedule relative to other large-class missions.

Much is at stake and you can watch it live (minus EDL and the speed of light) on NASA TV. Godspeed Curiosity !

- Update: Curiosity has landed. Raw images can be found here -

[1] A COMPLEXITY-BASED RISK ASSESSMENT OF LOW-COST PLANETARY MISSIONS: WHEN IS A MISSION TOO FAST AND TOO CHEAP?  David A. Bearden

[2] Rapid Cost Assessment of Space Mission Concepts through Application of Complexity-Based Cost Indices, Craig Peterson, James Cutts, Tibor Balint, James B. Hall

[3] Perspectives on NASA Mission Cost and Schedule Performance Trends, Presentation for the Future In-Space Operations (FISO) Colloquium 2 July 2008, Bob Bitten

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.

L1 Homotopy: A MATLAB Toolbox for Homotopy Algorithms in L1 Norm Minimization Problems -implementation -

Salman Asif sent me the following:

Dear Igor,

Thanks for mentioning our paper on your blog. You announced it before I had put it on my website, amazing!

I have uploaded the paper on my website and the code related to iterative and adaptive reweighting in the homotopy toolbox.

Paper can be found @ http://users.ece.gatech.edu/~sasif/Research/AR_rwtL1_2012.pdf

and code @ http://users.ece.gatech.edu/~sasif/homotopy/

Thanks,

-Salman

Thanks Salman ! The page for the implementation is L1 Homotopy: A MATLAB Toolbox for Homotopy Algorithms in L1 Norm Minimization Problems

The paper is: Fast and Accurate Algorithms for Re-Weighted l_1-Norm Minimization by M. Salman Asif and Justin Romberg. The abstract reads:

To recover a sparse signal from an underdetermined system, we often solve a constrained `1-norm minimization problem. In many cases, the signal sparsity and the recovery performance can be further improved by replacing the `1 norm with a “weighted” `1 norm. Without any prior information about nonzero elements of the signal, the procedure for selecting weights is iterative in nature. Common approaches update the weights at every iteration using the solution of a weighted `1 problem from the previous iteration.

In this paper, we present two homotopy-based algorithms that efficiently solve reweighted `1 problems. First, we present an algorithm that quickly updates the solution of a weighted `1 problem as the weights change. Since the solution changes only slightly with small changes in the weights, we develop a homotopy algorithm that replaces the old weights with the new ones in a small number of computationally inexpensive steps. Second, we propose an algorithm that solves a weighted `1 problem by adaptively selecting the weights while estimating the signal. This algorithm integrates the reweighting into every step along the homotopy path by changing the weights according to the changes in the solution and its support, allowing us to achieve a high quality signal reconstruction by solving a single homotopy problem.

We compare the performance of both algorithms, in terms of reconstruction accuracy and computational complexity, against state-of-the-art solvers and show that our methods have smaller computational cost.

In addition, we will show that the adaptive selection of the weights inside the homotopy often yields reconstructions of higher quality.

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.