Fast recovery from a union of subspaces
We address the problem of recovering a high-dimensional but structured vector from linear observations in a general setting where the vector can come from an arbitrary union of subspaces. This setup includes well-studied problems such as compressive sensing and low-rank matrix recovery. We show how to design more efficient algorithms for the union-of-subspace recovery problem by using approximate projections. Instantiating our general framework for the low-rank matrix recovery problem gives the fastest provable running time for an algorithm with optimal sample complexity. Moreover, we give fast approximate projections for 2D histograms, another well-studied low-dimensional model of data. We complement our theoretical results with experiments demonstrating that our framework also leads to improved time and sample complexity empirically.
In this paper, the authors consider the problem of signal recovery from a union of subspaces (UoS). UoS problems are a generalization of several structurally constrained problems, such as matrix completion and sparse regression. They show that one can obtain fast algorithms for UoS problems by considering an iterative projection scheme, and obtain highly accurate results even when the projections are approximate. A key insight is that they employ TWO approximate projections, onto what they call the “head” and “tail” subspaces. They apply their results to some canonical cases and show that the proposed methods are faster than methods that require exact projections, while not compromising on accuracy of the recovered signals. 
The paper is well written, and is very relevant. My only issue is that, while the motivation to propose the methods is that of scalability, the authors do not exlpicitly show that their methods are significantly faster than methods requiring exact projections on very large datasets. However, I recommend an accept since I think this addition in the paper is fairly trivial to do.   MAJOR COMMENTS: equation (2) only applies if the underlying optimization you intend to solve is least squares with a constraint. In the general case, the second term in the parenthesis will be the gradient of a generic loss function.   I expected Definitions 3 and 4 to be symmetric. Is there a reason why c_T = 0 is possible in def. 3 but not in 4?   line 160: recent advances in greedy methods obviate the need for the full SVD. Instead, they only require the top singular value to be computed, getting an order of magnitude improvement. Of course, these methods avoid exact projections but it might be prudent to mention the existence of such methods.  Line 218: How come there is no dependence on \gamma? won’t a simple counting argument yield \gamma even in a lower bound?  Lines 276-278: the explanation here seems to suggest that the order of projections (head first, then tail) is important. Is this correct? What will happen if one reverses the order?  Line 287: The U \otimes U_H \otimes U_T RIP condition is different from the usual (U \otimes U \otimes U) RIP conditions one might assume. Can you comment on this distinction and also compare? Maybe provide an example to indicate whether it is tighter or looser.  Figures 1-3: I suggest a comparison with other, non SVT based methods for low rank matrix recovery as well. greedily adding one SV at a time is significantly faster, and has been shown to perform very well. Also these greedy projections can be approximate (using power methods for example)   A key point you make is that IHT based schemes with approximate projections are faster than SVT based methods. Could you please provide runtimes on larger matrices (order 10K or more? ). More importantly, there should be sizes at which SVT with exact projections becomes infeasible. It might be good to see where that transition occurs.     MINOR COMMENTS: Line 63 : is there a reference for results for sparse PCA?  Definitions 3 and 4 : Do you need the constants to be bounded by 1 and not 0?  In theorem 5, should the \theta in the log terms be \theta^*?  line 157: replace “can be” with “is”. you already mention that r << d_1   line 162: an —> and  Theorems 7 and 8: what are the typical values of epsilon and zeta that one considers? a small epsilon will mean that zeta has to be large. eps = 1e-2 means that zeta has to be close to 10 atleast right? That makes the run time O(d^11) which is prohibitive.   Line 212: Please state the natural structural conjecture here.   Line 293: for the sake of completion, please provide the sample complexities for the cases you consider in the main paper as well.