Friday, June 13, 2008

CS: Advances in Numerical Harmonic Analysis, MDL and CS, Surveillance camera, Sound Classification, CVX and a workshop and a seminar.

Massimo Fornasier has a presentation on Advances in Numerical Harmonic Analysis. The outline of the talk is:

1 Frames in Hilbert spaces: towards the sparsity concept
  • Definitions and main properties
  • Gabor and wavelet frames
  • Local construction of global frames
  • -wave packets and -modulation spaces
  • Open problems and conjectures in frame theory

2 Finite frames and random ensembles
  • Compression and Compressed sensing (CS)
  • Optimal performances in CS
  • Restricted Isometry Property and fundamental open questions

His main area of research is what is called Compressive Algorithms. A presentation can be found is this poster and in his habilitation.

The second presentation with the same title has the following outline:

1 Sparse recovery
  • Sparsity, compressed sensing, and applications
  • l_1-minimization: re-weighted least square method
2 Accelerations
  • Projected gradient algorithms
  • Subspace correction methods (domain decompositions)
  • Applications of sparse recovery
3 Joint sparsity
  • Motivation
  • A new sparsity measure and alternating minimization algorithm
  • Firm-thresholding algorithms
  • Applications: color inpainting and art restoration
Also found on the internets these two papers, only the first one is available:

Determining canonical views of 3D object using minimum description length criterion and compressive sensing method by Ping-Feng Chen and Hamid Krim. The abstract reads:

In this paper, we propose using two methods to determine the canonical views of 3D objects: minimum description length (MDL) criterion and compressive sensing method. MDL criterion searches for the description length that achieves the balance between model accuracy and parsimony. It takes the form of the sum of a likelihood and a penalizing term, where the likelihood is in favor of model accuracy such that more views assists the description of an object, while the second term penalizes lengthy description to prevent overfitting of the model. In order to devise the likelihood term, we propose a model to represent a 3D object as the weighted sum of multiple range images, which is used in the second method to determine the canonical views as well. In compressive sensing method, an intelligent way of parsimoniously sampling an object is presented. We make direct inference from Donoho1 and Candes'2 work, and adapt it to our model. Each range image is viewed as a projection, or a sample, of a 3D model, and by using compressive sensing theory, we are able to reconstruct the object with an overwhelming probability by scarcely sensing the object in a random manner. Compressive sensing is different from traditional compressing method in the sense that the former compress things in the sampling stage while the later collects a large number of samples and then compressing mechanism is carried out thereafter. Compressive sensing scheme is particularly useful when the number of sensors are limited or the sampling machinery cost much resource or time.

The application of Compressive Sensing technique on a stationary surveillance camera system by Jing Zheng and Eddie Jacobs. The abstract reads:
Compressive Sensing (CS) is a recently emerged signal processing method. It shows that when a signal is sparse in a certain basis, it can be recovered from a small number of random measurements made on it. In this work, we investigate the possibility of utilizing CS to sample the video stream acquired by a fixed surveillance camera in order to reduce the amount of data transmitted. For every 15 continuous video frames, we select the first frame in the video stream as the reference frame. Then for each following frame, we compute the difference between this frame and its preceding frame, resulting in a difference frame, which can be represented by a small number of measurement samples. By only transmitting these samples, we greatly reduce the amount of transmitted data. The original video stream can still be effectively recovered. In our simulations, SPGL1 method is used to recover the original frame. Two different methods, random measurement and 2D Fourier transform, are used to make the measurements. In our simulations, the Peak Signal-to-Noise Ratio (PSNR) ranges from 28.0dB to 50.9dB, depending on the measurement method and number of measurement used, indicating good recovery quality. Besides a good compression rate, the CS technique has the properties of being robust to noise and easily encrypted which all make CS technique a good candidate for signal processing in communication.
The dimensionality reduction aspect of compressed sensing that yields studies on simpler manifolds (coordinates size of the new features are smaller) have been looked at by Jort Gemmeke in the voice case. The issue is that when one wants to classify or imput voice/sounds tracks, one deals with very large training datasets. It looks like voice is not the only field where random projection can be used as a dimensionality reduction technique as shown in the next two articles by Neta Rabin, Alon Schclar, Valery Zheludev and Amir Averbuch.

Detection of moving vehicles via dimensionality reduction . The abstract reads:
Automatic vehicle detection is a common task in security and surveillance systems. A microphone is placed in a designated area and a hardware/software system processes the sounds that are intercepted by the microphone to detect vehicles as they pass by in the designated area. We propose a novel algorithm for real-time automatic detection of vehicles. The proposed scheme uses dimensionality reduction and utilizes ideas from compressed sensing.

Wavelet based acoustic detection of moving vehicles. The abstract reads:
We propose a robust algorithm to detect the arrival of a vehicle of arbitrary type when other noises are present. It is done via analysis of its acoustic signature against an existing database of recorded and processed acoustic signals to detect the arrival of a vehicle of arbitrary type when other noises are present. To achieve it with minimum number of false alarms,we combine a construction of a training database of acoustic signatures signals emitted by vehicles using the distribution of the energies among blocks of wavelet packet coefficients with a procedure of random search for a near-optimal footprint. The number of false alarms in the detection is minimized even under severe conditions such as: the signals emitted by vehicles of different types differ from each other, whereas the set of non-vehicle recordings (the training database) contains signals emitted by planes, helicopters, wind, speech, steps, etc. The proposed algorithm is robust even when the tested conditions are completely different from the conditions where the training signals were recorded. The proposed technique has many algorithmic variations. For example, it can be used to distinguish among different types of vehicles. The proposed algorithm is a generic solution for process control that is based on a learning phase (training) followed by an automatic real-time detection.
When are we going to see Compressive Microphones is my question ?

We now have version 1.2 of the CVX package by Michael Grant, Stephen Boyd and Yinyu Ye
and some news:

Latest news

Support for the exponential family of functions

CVX version 1.2 now supports problems involving exponentials, logarithms, and entropy functions! A novel successive approximation approach has been developed to facilitate this improvement. Please see the user’s guide for more details.

Notice to users of Matlab R12.1 (6.1)

In order to facilitate some upcoming developments for CVX, we have decided that it will be necessary to discontinue support for Matlab 6.1. This change will occur at some point this summer, at which point CVX will require the use of Matlab version 6.5 or newer. If you currently use Matlab 6.1, please contact us to discuss alternatives.

A Call for Papers for the ICA Research Network International Workshop to be held on 25-26 September, 2008 in Liverpool, U.K.

The ICA Research Network is sponsored by the Engineering and Physical Sciences Research Council (EPSRC) in the U.K., and is aimed at improving communications in the area of Blind Source Separation (BSS) and Independent Component Analysis (ICA). The 2008 ICA Research Network Workshop will be held at the University of Liverpool covering the latest developments and techniques in the area of source separation and ICA. Submissions from international participants are most welcome.


The workshop will feature keynote addresses and technical presentations (oral and poster), which will be included in the registration. Papers are solicited on topics in the area of source separation or ICA, including but not limited to: Algorithms and Architectures (Non-linear ICA, Probabilistic Models, Sparse Coding, etc), Theory (Optimization, Complex Methods, Time-Frequency Representations, etc), Applications (Audio, Bio-Informatics, Biomedical Engineering, Communications, Finance, Image Processing, Psychology, etc), and novel methods (compressed sensing, non-negative matrix factorization).

A special feature of this workshop will be a special poster session where authors will have the opportunity to present their current work in progress. Authors should indicate their preference at the submission stage and submit short papers.

Important Dates/Deadlines

Submission of papers: 17 June, 2008
Notification of acceptance : 17 July, 2008
Submission of camera-ready accepted paper : 07 August, 2008
Early registration and author registration : 07 August, 2008
Final date for registration : 08 September, 2008
Workshop : 25-26 September, 2008


and a Theory seminar at the Technion on Expander codes, Euclidean Sections, and Compressed Sensing Venkatesan Guruswami, (Washington University)

Date:Sunday, 15.6.2008, 13:30
Place: Room 337-8 Taub Bld.

Classical results in high-dimensional geometry from the 1970's state that a random subspace of R^N of dimension N/2 has "distortion" O(1) w.h.p where the distortion is measured by sqrt{N} times the largest ratio of the L_2 to L_1 norms of a vector in the subspace. (So each vector in the subspace has its mass spread nearly evenly over a constant fraction of the coordinates.) This result is a particular example of the use of the probabilistic method, a technique which is ubiquitous in asymptotic convex geometry. Similar randomized geometric constructions arise in areas like dimensionality reduction and compressed sensing, but it seems that such objects are very hard to come by explicitly.

We will describe constructions inspired by expander codes that can be used to produce subspaces with distortion nearly as good as a random subspace either explicitly or with sublinear randomness. Specifically, we construct an explicit subspace of R^N with dimension N(1-o(1)) and distortion (slightly worse than) poly(log N). The construction combines various ingredients such as Ramanujan graphs, sum-product theorems in finite fields, and Kerdock codes/mutually unbiased bases. We are also able to construct subspaces of R^N of proportional dimension with O(1) distortion using N^delta random bits for any constant delta > 0 (and hence deterministically in sub-exponential time). The talk will also briefly discuss connections to sparse signal recovery (i.e., compressed sensing).

Credit: NASA / JPL / MSSS, A crater on Mars resembling a "happy face". It was acquired by the Context Camera (CTX) on Mars Reconnaissance Orbiter on January 28, 2008. Via the planetary society blog.

No comments: