Friday, July 26, 2013

Around the blogs in 80 Summer hours

Quite a few interesting blog entries in these past two weeks:


Dusty THREE TALKS FROM SAMPTA 2013
Bob
Rich
Hein

David AI and Free Will: When do choices exist?
Jeremy Announcing my New Book: Exploring Arduino
Larry

Andrej CVPR 2013 reading list
Dan Playing detective with rolling shutter photos
John Some things can’t be done slowly
Anand
Djalil

Vladimir
in that entry one can find the publication of one of Nuit Blanche's reader
Patrick R. Gill and David G. Stork
Drs. Gill and Stork introduce a new type of diffractive element based on odd-symmetry phase gratings. Spiral arrangements of these gratings over photo sensors constitute a new class of unprecedentedly small computational camera.
Avinash Kumar, Patrick R. Gill, Thomas Vogelsang, and David G. Stork
During this presentation, Rambus engineers will describe novel methods of computing sharp shadows and depth estimates of objects immersed in highly scattering media using multi-scale structured transmissive illumination, such as modified Hadamard tiles.

While on Nuit Blanche, we had

This image was taken by Navcam: Right B (NAV_RIGHT_B) onboard NASA's Mars rover Curiosity on Sol 344 (2013-07-25 15:42:34 UTC). 

Image Credit: NASA/JPL-Caltech 

Wednesday, July 24, 2013

Recovery conditions for Greedy Solvers

Boris Mailhe just sent me the following:


Hi Igor,

Here is a quick summary of our 2 papers with Bob Sturm and Mark Plumbley (the ICASSP proceedings are not on IEEExplore yet):


In these 2 articles we analyze whether for a given dictionary, sparser signals are always easier to recover by greedy algorithms. As a background, Joel Tropp's approximations of the Exact Recovery Condition (ERC) using the coherence or cumulative coherence scale monotonically with the size of the support. However, Mark Plumbley proved in an earlier article that the ERC itself does not. In this work we proved three main results:
1) (IEEE Trans. Info. Theory) Plumbley's proof used non-normalized dictionaries, but the formulation of the ERC that gives recovery guarantees differs in that case. So while Plumbley's result is mathematically correct, it cannot be extended into a result on sparse recovery.
2) (ICASSP) There can be a support I that is uniformly recoverable by OMP and a sub-support I' included in I that is not,
3) (ICASSP) but for any dictionary Phi and any s less than spark(Phi)/2 (the only range that matters since sparse representations are not all unique for s greater or equal to spark(Phi)/2), if all supports of size s are uniformly recoverable by OMP, then all supports of smaller size also are.
....
Best wishes,

Here are the papers:

Résumé : It is shown that Theorem 10 (Non-Nestedness of ERC) in [Plumbley, IEEE Trans. Info. Theory, vol. 53, pp. 3188, Sep. 2007] neglects the derivations of the exact recovery conditions (ERCs) of constrained 1-minimization (BP) and orthogonal matching pursuit (OMP). This means that it does not reflect the recovery properties of these algorithms. Furthermore, an ERC of BP more general than that in [Tropp, IEEE Trans. Info. Theory, vol. 50, pp. 2231, Oct. 2004] is shown.





Boris Mailhé  1, Bob L. Sturm, Mark D. Plumbley

Résumé : In this work, we study the links between the recovery proper- ties of sparse signals for Orthogonal Matching Pursuit (OMP) and the whole General MP class over nested supports. We show that the optimality of those algorithms is not locally nested: there is a dictionary and supports I and J with J included in I such that OMP will recover all signals of sup- port I, but not all signals of support J. We also show that the optimality of OMP is globally nested: if OMP can recover all s-sparse signals, then it can recover all s′-sparse signals with s′ smaller than s. We also provide a tighter version of Donoho and Elad's spark theorem, which allows us to com- plete Tropp's proof that sparse representation algorithms can only be optimal for all s-sparse signals if s is strictly lower than half the spark of the dictionary.


On Theorem 10 in “On Polar Polytopes and the Recovery of Sparse Representations”Sturm, B.L. ;  Mailhe, B. ; Plumbley, M.D.
It is shown that Theorem 10 (Non-Nestedness of ERC) in [Plumbley, IEEE Trans. Inf. Theory, vol. 53, pp. 3188–3195, Sep. 2007] neglects the derivations of the exact recovery conditions (ERCs) of constrained $ell_{1}$ -minimization (BP) and orthogonal matching pursuit. This means that it does not reflect the recovery properties of these algorithms. Furthermore, an ERC of BP more general than that in [Tropp, IEEE Trans. Inf. Theory, vol. 50, pp. 2231–2242, Oct. 2004] is shown.


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.

Tuesday, July 23, 2013

Videos: Workshop on Sparsity, Compressed Sensing and Applications

Boris Mailhe sent me the following:

 the videos of the Workshop on Sparsity, Compressed Sensing and Applications are now online at http://c4dm.eecs.qmul.ac.uk/events/sparse-workshop-09-05-12/

Best wishes,
Boris

Thanks Boris

Here is the list of abstracts and videos:

Abstracts
  • Rémi Gribonval, INRIA (keynote speaker): "Sparse Audio Models for Inverse Audio Problems"
Inverse problems are ubiquitous in audio processing, from the restoration of saturated single channel audio to the localization of audio sources using arrays of two or more microphones. In the last decade, a solid mathematical and algorithmic framework has emerged to address such problems, based on the notion of sparse atomic decompositions in signal dictionaries. In practice, choosing a dictionary often requires prior expert knowledge. I will discuss some recent alternatives to pre-chosen dictionaries, including designs exploiting the underlying physics, as well as data-driven approaches where the model is learnt from a training corpus.
  • Stefan Bleeck, University of Southampton:  "How Sparse Coding Can Be Used to Improve Hearing Aids and Cochlear Implants"
Language is the key to the world. However, speech intelligibility and thus auditory communication suffers when hearing is impaired. The total annual cost of hearing impairment in the EU has been estimated to be €224 billion p.a. In the UK alone 6 million more people could benefit from a hearing aid (HA or cochlear implant CI) than currently do so (worth £18 billion p.a.). These costs are mainly because of economical inactivity due to the hearing loss. The main reason why HA are not taken up is that they do not work well in noisy situations people are often in, especially in an social environment.
In our group we aim to develop novel speech enhancing strategies based on statistical information approaches inspired by brain-physiology. Current hearing aids are mainly amplification devices with little consideration of physiological principles. We have developed and evaluated various sparse coding algorithms based on ICA, PCA and NMF. In my presentation I will give an overview of the problem, and present current approaches how to overcome the problem using sparse coding algorithms. I will also show latest results from evaluation using a ‘target machine’ which allows psychophysical experiments with cochlear implant and hearing aid users in real time.
  • Wei Dai, Imperial College: "Low Rank Matrix Completion: a Smoothed L0-Search"
Low-rank matrix completion aims at inferring the missing entries from partial observations of a low-rank matrix. While many techniques for solving this problem originate from compressed sensing reconstruction, there is a fundamental difference: how to perform the l_0 search for matrix completion is not conceptually clear. Formulating the l_0 search as an optimization problem, we shall argue that the major difficulty in solving this optimization problem, surprisingly, is not local minima or saddle points but singular points. To address the singularity issue, we propose a new objective function that is continuous everywhere. The new objective function is a good approximation of the original objective function in the sense that in the limit, the former is the best possible lower semi-continuous approximation of the latter. We formulate the matrix completion problem as the minimization of the new objective function and design a quasi-Newton method to solve it. Simulations demonstrate that the new method achieves excellent numerical performance.
  • Boris Mailhé, Queen Mary University of London: "Audio Declipping Using Sparse Multiscale Representations"
Audio acquisition devices (microphones, analog to digital converters,…) typically have a maximum input level. Recorded samples that would exceed that value are instead clipped to it. Declipping is the task of restoring the original amplitude of those clipped samples. This presentation will show how a sparse modelling of the clean samples can help to retrieve the clipped ones both on synthetic clippings and real recorded signals. It will also present a new multi-scale approach that enhances the quality of the reconstruction in the most challenging cases with more clipped samples that form longer intervals.
  • Yaochun Shen, University of Liverpool: "Experimental Implementation of Compressed Terahertz Imaging"
Over the past decade, there has been great interest in the study of compressed sensing, where the number of physical measurements is much smaller than that of pixels in the reconstructed image. Such a compressed sensing approach is particularly attractive for imaging applications at terahertz frequencies where compact and sensitive detector array is currently not readily available. Here we report the experimental implementation of a terahertz pulsed spectroscopic imaging system based on the conceptof compressed sensing. A single-point terahertz detector was used to measure the terahertz waveforms transmitted through a sample and a terahertz spatial modulator. Terahertz time- and frequency-domain images of the sample were subsequently reconstructed. Two terahertz spatial modulator were used: one is a set of optimised binary masks and the other is a spinning disk with random patterns. We demonstrate that both the spatial distribution and the spectral characteristics of a sample can be obtained by this means. Compared with conventional terahertz pulsed imaging, no raster scanning of the object is required, and ten times fewer terahertz spectra need be taken.  It is therefore ideal for real-time imaging applications. 
  • Andy Stove, Thales UK: "Compressive Sensing for Radar and Electronic Warfare"
Radar data should be an ideal candidate for compressive sensing since the input data rates are very high, for example up to 1Gbit/sec or even more, being driven by the required range resolution, whereas the output information rate is very low - it can typically be transmitted down a telephone line. This can also be looked at by noting that the density of targets of interests is very low whilst the volumes which are surveyed are very large - radar is uniquely capable of long-range surveillance.
Similar issues apply to the Electronic Warfare receivers which try to intercept the radar signals, where the data rates are also very high, but much of the time/frequency space is, again, only sparsely populated with signals, but many signals are concentrated in small regions of the space.
For both applications, the most modest application of compressive sensing would be to reduce the amount of digital data which must be stored or communicated. It is desirable that the data can be stored for future analysis and it is also becoming increasingly important to be able to share it between different sensors, which, without compression, would require vast communication bandwidths.
The second approach would be that if suitable data domains can be identified, it may also be possible to pre-process the data before the analogue-to-digital converters in the receivers, to reduce the demands on these critical components.
The most ambitious use of compressive sensing would be to find ways of modifying the radar waveforms to change the domain in which the information is represented, to reduce the data rate at the 'front end' of the receiver, i.e. to make the whole receiver much better matched to the information which we really want to acquire.
The presentation will introduce the principal issues in radar design and electronic warfare receiver design. It will describe the issues where compressive sensing should be able to help. It will discuss what has already been achieved in compressive sensing in these fields and will highlight the open issues which remain.
  • Jared Tanner, University of Oxford: "Empirical Testing of Sparse Approximation and Matrix Completion Algorithms on Distributed Systems"
Empirical testing is a useful technique to explore the behaviour of algorithms for which theory has not yet fully explained their behaviour.  We discuss the type of testing that can be conducted to establish conjecture.  Results are presented for l1-regularization, for which the conjecture has been proven, as well as iterative hard thresholding algorithms for both compressed sensing and matrix completion.
  • Mehrdad Yaghoobi, University of Edinburgh: "Cosparse Low-Dimensional Signal Modelling"
A new algorithm for analysis operator learning will be presented in this talk, to generalise the framework and make it more scalable. The problem of analysis operator learning can be formulated as a constrained optimisation problem. A suitable constraint is necessary to make the optimisation well-posed. Such constraints have already been introduced and the problem has been approximately solved using the projected gradient or geometric gradient descent methods. Such constraints will briefly be explored in this talk and it will be shown why other simpler constraints are insufficient.
A relaxation for the constrained analysis operator learning framework will be proposed in this talk. The relaxation has been suggested here to, a) reduce the computational complexity of the optimisation and b) include larger set of admissible operators. It will be shown that an appropriate relaxation can be useful to present a projection-free optimisation algorithm, while preventing the problem to become ill-posed. Although the optimisation program is now unconstrained, the relaxed objective is still not convex and it is thus not always possible to find the global optimum. However, when a rich set of training samples are given, it is empirically demonstrated that the desired synthetic analysis operator is recoverable, using the new relaxed formulation.
 



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.

Monday, July 22, 2013

2nd GraphLab workshop videos release

Danny Bickson just let me know that the videos of the second GraphLab meeting that took place at the beginning of the month. All the videos are at



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.

Call for Expression of Interest in hosting "SPARS15"

Remi Gribonval just sent me the following:

Dear Igor,
In the follow-up of SPARS'13, the SPARS Steering Committee is looking for hosts for the following SPARS meeting. 
Would you mind relaying this on Nuit-Blanche ? Thanks!
All the best, 
Remi.


Sure here it is:
----
Dear colleagues,
In the follow-up of the workshop SPARS'13 on Signal Processing with Adaptive/Sparse Representations, the SPARS Steering Committee is looking for hosts for the following SPARS meeting.
The SPARS workshop is expected to run about each 24 months, so the next workshop would most likely be held mid 2015.
(As a past host myself, I know that this is an exciting and rewarding opportunity to make a major contribution to the community!)
If you and/or colleagues would like to host the next workshop, or think this sounds interesting and would like to know more, please send a brief email as an "Expression of Interest" to the new chair of the SPARS Steering Committee, Jalal Fadili <Jalal.Fadili@ensicaen.fr>.
Full details are not required at this stage, but as much of the following information (if known) would be helpful:
* Proposed location / venue
* Names of organizers
* Suggested dates
* Funding strategy
* Other information if available (accommodation options, travel, costs, other special features)
Please send any initial "expressions of interest" by email to Jalal Fadili <Jalal.Fadili@ensicaen.fr> by September 15.
The SPARS Steering Committee will then discuss these expressions of interest and we will get back to you.
In the meantime, if you have any queries, please let me know.
Best wishes, 
Rémi Gribonval.
---
Note: the Steering Committee will take the following elements into particular consideration when assessing propositions:
* Format: SPARS is aimed to be a "human size" workshop: not more than 200 participants, one or at most two parallel tracks, and ample time for discussions.
* Student-friendliness: support to students, e.g., through reduced fee and/or travel grants, is expected. 
* Abstract 'only': SPARS is primarily intended to be a forum for exchanges at the frontier between applied math and electrical engineering. To accommodate the different publishing cultures of these communities,  SPARS13 only requested a mandatory 1-page abstract, but full papers  were not required. The organizers of the next edition are free to consider optional proceedings for authors who would wish to provide an extended paper.
* Funding: Bidders should show that they can provide / have applied for a grant to support the organization of the event.
* Accessibility & affordability: ease of access and affordability may be preferred to fancy locations.
* Timing: time conflicts with other sparsity related workshops such as SaMPTA, SPIE Wavelets&Sparsity, etc. should be avoided if possible.

--
----------------------------------------------------------------------
Rémi Gribonval - Directeur de Recherche Inria
PANAMA Research Group, IRISA (Inria & CNRS)
Campus de Beaulieu, 35042 Rennes cedex, France

----------------------------------------------------------------------




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, July 21, 2013

Videos of the ICML2013 meeting - part II


Track A: Nearest Neighbor and Metric Learning



Compressed Sensing 2



Track B: General Methods



Reinforcement learning 2



Track C: Transfer Learning



Topic Modeling 1



Track D: Statistical Learning and Inference



Deep Learning and Neuroscience



Compressed Sensing 3



Reinforcement Learning and Time Series



Topic Modeling 2



Track A: Invited Orals



Track A: Online Learning 1



Track A: Dimensionality Reduction and Semi-Supervised Learning



Session


Track B: Feature Learning



Track B: Optimization and Integration



Tutorials



Track C: General SVM and Decision Tree Methods



Track C: Vision



Track D: Spectral Learning and Tensors



Track D: Learning Theory II


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.

Printfriendly