• View
• Edit
• History
• Print

2014-2015

Seminars are usually held on Friday from 11:00 to 12:00 in the main seminar room (Euler Room - A002) of the Building Euler.
If you wish to receive the seminar announcements, please send an email to sympa2@listes.uclouvain.be.
The subject line should be 'subscribe large-graphs-networks yourname' where yourname is your first and last name.

Motivated by spectral or eigen-analysis based algorithms for the identification of cliques and communities in large graphs, we consider the properties of the eigenvalues and eigenvectors of low-rank "signal" matrices that are corrupted by "noise" random matrices. Additional applications addressed by this theory include matrix completion, spectral clustering, and Gaussian mixture cluster analysis in machine learning.

We provide an application-independent approach that brings into sharp focus a fundamental informational limit of the recovery of the low-dimensional signal subspaces (or matrices) using eigen-analysis. In other words, we demonstrate the presence of a phase transition which separates a regime where eigen-analysis "works" from a regime where eigen-analysis fails. Building on this analytical success, we highlight the random matrix origin of this informational limit, the connection with "free" harmonic analysis and discuss implications for structure recovery and identification in high-dimensional matrix-valued datasets such as graphs.

Online reputation systems are an effective way to protect users from fraud and provide incentives for them to cooperate and contribute to the system. Their basic functionality yields on aggregating the history of user interactions in one reputation value per user. Even though several reputation systems such as those of eBay, Amazon and eLance function effectively on a worldwide scale, they rely on a single point of control. Nevertheless, growing privacy concerns and popularity of applications on mobile devices motivate the use of decentralized reputation systems. Due to the highly dynamic behavior of users and the scarcity of resources, several challenging scalability and security issues arise. In this presentation, I will describe algorithms for decentralized reputation systems developed during my PhD thesis with the Paralllel and Distributed Systems group at TUDelft. Those algorithms exploit the graph structure induced by the user interactions in decentralized reputation systems.

We routinely compute extreme eigenvectors of symmetric matrices. We also frequently minimize indefinite quadratic forms over balls (the trust-region subproblem). But those problems are not convex. What is the Convexity Police doing?

As it turns out, these problems /are/ convex, but in a higher dimensional space (lift and relax). And, the corresponding relaxations are /always/ tight. This remarkable fact follows from a simple, generic theorem about the rank of the solutions of semidefinite programs. I will state and prove that theorem (spoiler alert: Schur helps), and show how it applies to the aforementioned problems.