Workshop on Sparsity, Compressed Sensing and Applications
Centre for Digital Music, Queen Mary University of London
Monday, 5 November 2012 from 10:30 to 17:00 (GMT)
London, United Kingdom
One day workshop on sparsity, compressed sensing and applications.
Mark D. Plumbley
Phone: +44 20 7882 7986
10.30 - 11.00: Welcome coffee
There will be an opportunity to continue discussions after the Workshop in a nearby Pub/Restaurant.
The workshop is free to attend but registration is mandatory.
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.
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.
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.
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.
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 concept of 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.
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.
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.
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.
The Event will take place in Room 1.13a, Bancroft Building, Queen Mary University of London, Mile End Road, London E1 4NS. The venue is easily accessible by public transport. It is within a five minute walk of both Mile End Underground station (Central, District, and Hammersmith & City lines) and Stepney Green Underground station (District, and Hammersmith & City lines).
Suggested hotels for staying before or after the workshop: