Ahmed El Alaoui

photo_me 

Ph.D. student, Electrical Engineering and Computer Sciences, UC Berkeley.

Co-advised by Michael Jordan and Benjamin Recht.

| Papers | Coursework | Teaching | code |

Contact
University of California, Berkeley
652 Sutardja Dai Hall
Berkeley, CA 94720-1720
Email me at elalaoui at eecs dot berkeley dot edu

Research interests

My research interests lie somewhere between mathematical statistics and optimization. I am generally interested in the design and analysis of algorithms that attempts to extract information from limited and corrupted data, and studying the various tradeoffs that may appear in the analysis of such algorithmic procedures, e.g. statistical accuracy vs. computational budget.

My work

While advised by Alex Bayen (2013-2014):

Tim Hunter, Ahmed El Alaoui, Alex Bayen: Computing the log-determinant of symmetric, diagonally dominant (SDD) matrices in near-linear time.

(To be submitted to SIAM Journal of Matrix Analysis and Applications)

We present an algorithm (that we call ultralogdet) that exploits recent ideas on graph sparsification to compute the log-determinant of a SDD matrix in time quasi-linear in the number of its non-zero entries. The core idea is the simple identity: log |A| = log |B| + log |B^{-1}A|, for two matrices A and B. We show that if B is a good approximation to A (in the spectral sense), the second term can be approximated by a Monte Carlo procedure. Then, given such a good B, all we have do is compute its log-det, which can in turn be approximated in a similar way. Now, a remarkable fact (Spielman and Teng ’04) is that for an input SDD matrix A, such a chain of good approximations can be obtained by working on a graph underlying the matrix A, and incrementally sparsifying it, i.e. cutting its edges. The obtained (sequence of) graphs have fewer and fewer edges while retaining the spectral properties of their predecessors. Once the last graph of the chain is small enough, its log-det is computed by brute force, and the overall approximation is shown to be epsilon-accurate for a running time of tilde{O}(textup{nnz}(A)/epsilon^2). More on graph sparsification and related problems on Daniel Spielman's page.

Cathy Wu, Ahmed El Alaoui, Cathal Coffey, Alexei Pozdnoukhov, Alex Bayen: Tractable flow inference using convex optimization with loop and cellular data.

(Submitted to the International Symposium on Transportation and Traffic Theory ’15)

We provide a tractable formulation for and solve the route assignment problem using novel techniques from convex optimization. Given origin-destination (OD) estimates for a region and link flow measurements at a number of links, we estimate the distribution of flows over a set of routes (the route flow). We propose a novel approach of using kernel methods from machine learning to estimate OD flows given aggregated counts of vehicles present on a part of the network (derived from the phones presence within each cell) for the current route flow estimate. We find a locally optimal solution for both OD flow and route flow by iterating between solving for each of these two problems.

About me

I am a first year Ph.D. student in Electrical Engineering and Computer Science at the University of California at Berkeley. I did my master's at Ecole Normale Supérieure and my undergrad at Ecole Polytechnique. I wrote my master's dissertation on probabilistic record linkage while working at Ecole des Ponts with Guillaume Obozinski.