In the matrix completion problem, one sees a few entries of an (approximately) low-rank matrix and hopes to (approximately) recover the entire matrix. This problem has gotten a lot of attention recently, partly due to its applicability to recommender systems. It is known that, by solving a convex program, the original matrix can be recovered with a number of observations that is linear in n. However, for current analyses of faster algorithms (with runtime linear in n), the number of samples additionally depends at least quadratically on the *condition number* of the matrix. In this wor

# Events

## Upcoming Events

There are currently no upcoming events scheduled. Please check back soon for more details.

## Recent Events

Personalized models often revolve around per-user parameters quantifying, say, an individual's interest in a certain product category or susceptibility to a certain type of advertisement, even after known features of the product and the person have been taken into account. Social networks offer an appealing way to make inferences about such parameters, the intuition being that one's parameter is "close'' to that of one's friends. We look at this basic scenario from two angles.

In high speed network measurement, such as in core Internet routers, there may only be a few nanoseconds available per packet for measurement purposes. Our objective is to be able to accurately measure the flow size distribution, that is the number of packets that belong to the same data transfer (think TCP connection), in such an environment. The flow size distribution is an important metric for traffic managment, profiling, and security purposes.

This work studies the problem of sequentially recovering a sparse vector x_t and a vector from a low-dimensional subspace l_t from knowledge of their sum m_t=x_t+l_t. If the primary goal is to recover the low-dimensional subspace where the l_t's lie, then the problem is one of online or recursive robust principal components analysis (PCA). An example of where such a problem might arise is in separating a sparse foreground and a slowly changing dense background in a surveillance video.