A Globally Optimal Solution to Low Rank Regression

In the Spring of my first year at UW (Spring 2016), I took a course on convex optimization algorithms. I was interested in low rank regression due to a research project I was working on. I played around with the formulation

 \min_W \|Y - XW\|_F^2\ \ \text{s.t.}\ \text{rank}(W) \leq k

It turns out that there is a closed form solution to this non-convex problem! The solution is based on the k-rank approximation theorem by Eckart, Young, and Mirsky. It also turns out that someone else independently discovered this in 2012 (check it out), and they analyzed the statistical properties of it. Anyways, I wrote a write up with proofs which you can find here: mid_quarter_report. I also included a closed form solution to the slightly more general problem

 \min_W \|Y - BW\Phi\|_F^2\ \ \text{s.t.}\ \text{rank}(W) \leq k

I have not seen this result published anywhere.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s