Computer Vision News - July 2019

Madeleine Udell is Assistant Professor of Operations Research and Information Engineering at Cornell University. She spoke to us ahead of her oral and poster, which she presented alongside Postdoctoral Associate Jicong Fan. Madeleine tells us that this work starts out with the problem of finding missing entries in data vectors. A classic well- understood approach to filling in missing entries in data sets is low-rank matrix completion. That assumes that all of the vectors lie in a low- dimensional subspace. If, for example, the vectors lie in a two-dimensional subspace, then knowing any two of their coordinates allows you to figure out all of the rest once you’ve learned the subspace. This work looks at the question, what happens if you want to fill in missing entries, but your vectors don’t live in a two-dimensional subspace, they live in a low- dimensional manifold? She asks us to imagine a one- dimensional manifold – just one curve – and imagine it in a 3D space. If the curve does anything remotely interesting, then the span of all the vectors on the curve is the complete 3D space. It’s not low rank; it’s full dimensional. You cannot use normal low-rank techniques to fill in the missing data, but there’s a clear structure. You’re on a one-dimensional manifold. It’s like a line. It’s very easy to see this curve. The question is, how can we see curves like this in higher- dimensional space? Madeleine explains: “ The way that we solve it is we take these vectors and we blow them up. We map them through a polynomial feature map. We take each of the points and we compute many, many polynomials in the coordinates that we have observed. Now our data lives in a much higher-dimensional space, and in that much higher- dimensional space, it is low dimensional. So, it actually lives on a low-dimensional subspace in this higher-dimensional space. The dimension of that subspace is probably larger than the ambient dimension of the original space, but it’s still low- dimensional in the ambient dimension of this blown-up space. The most important trick is the fact that after blowing up using this feature map, the resulting set of points is a low- dimensional subspace so that we can use ideas from low-rank matrix completion. ” Online High Rank Matrix Completion 28 DAILY CVPR Thursday Presentation Madeleine Udell