Date: Nov. 7th (Thu)
Time: 14:00 - 17:00 (with some coffee breaks)
Place: CELC Seminar room

(In the order of talks)
Speaker: Haiping Huang (JSPS research fellow, Tokyo Inst. of Tech., Japan)
Title: Entropy landscape analysis of the binary perceptron problem
Abstract: 
In artificial intelligence, a binary perceptron is a device classifying
patterns with many inputs by assigning individual weights to each input,
and the weights take binary values. Often, these weights have to be
inferred from a set of examples. However, it is difficult to find a
low-complexity algorithm to identify these weights. Statistical
physicists started to study this problem 25 years ago by analyzing
the solution space of binary weights. However, the relation between
the solution space structure and the algorithmic hardness has not yet
been fully understood. Our work demonstrates two interesting effects
in the solution space through the entropy landscape analysis:

(1) clustering refers to the fragmentation of the solution space into
well-separated clusters; (2) freezing refers to the appearance of
isolated solutions instead of clusters of exponentially many close-by
solutions.

Our results explain the observed glassy behavior of stochastic local
search heuristics and are also expected to shed light on other hard
problems in information processing (e.g., channel coding systems).

Speaker: Mikko Vehkapera (Aalto University, Finland and KTH, Sweden)
Title: Compressed sensing with correlated measurement matrices and 
application to metagenomics
Abstract: 
In the first part of the talk, we review some analytical results 
that characterize the performance of convex relaxation
based recovery algorithms used in compressed sensing. 
In particular we are interested in the case where the 
measurement matrix is of some other type than the standard
Gaussian ensemble. Using replica method, we show that under certain 
conditions there are matrix ensembles that offer improved 
performance of convex relaxation based recovery when compared 
to the standard Gaussian ensemble.

The second part of the talk consists of examining a practical 
problem of estimating bacterial community composition from
a high-throughput sequenced sample. Current estimation methods 
that provide accurate results are typically computationally complex
and require the use of computing cluster. Using a method inspired by 
sparsity enforcing techniques from compressed sensing, we propose a 
fast solution to the aforementioned metagenomics problem. The model
solution is obtained both by using convex optimization tools and 
through a greedy iterative algorithm and shown to provide good
accuracy-complexity tradeoff for the current problem.

END OF ANNOUNCEMENT