Low-Rank Matrix and Tensor Completion via Adaptive Sampling
We study low rank matrix and tensor completion and propose novel algorithms that employ adaptive sampling schemes to obtain strong performance guarantees. Our algorithms exploit adaptivity to identify entries that are highly informative for learning the column space of the matrix (tensor) and consequently, our results hold even when the row space is highly coherent, in contrast with previous analyses. In the absence of noise, we show that one can exactly recover a n ⇥ n matrix of rank r from merely ⌦(nr 3/2 log(r)) matrix entries. We also show that one can recover an order T tensor using ⌦(nr T 1/2 T 2 log(r)) entries. For noisy recovery, our algorithm consistently estimates a low rank matrix corrupted with noise using ⌦(nr 3/2 polylog(n)) entries. We complement our study with simulations that verify our theory and demonstrate the scalability of our algorithms.
the paper suggests a matrix reconstruction algorithm 
      for matrices in case of incoherence in the columns only, not 
      necessarily in the rows. a similar result for tensors, where incoherence 
      is in all dimensions except the last one. the idea is very 
      simple. for matrices, it goes like this: recovering a column-incoherent 
      rank-r matrice amounts to recovering (a basis of) the column space, 
      because given the column space you can recover each column by sampling 
      order of r log r entries and solving equations. to get the column space 
      basis, you greedily "grow" a basis by, at each iteration, trying all 
      columns until you find one column which is not spanned by the columns 
      you already have. checking whether a column is not spanned can be done 
      again by sampling O(r log r) entries of that column. each time you 
      find column, you add it to your basis by completely uncovering it, 
      hence this is an adaptive sampling strategy. it seems like a 
      reasonable idea, although i didn't check the proof. the same idea is 
      applied to tensors in a recursive fashion. compared to nuclear 
      norm minimization techniques, the paper claims that this algorithm gives 
      better bounds in certain cases where the incoherence of the rows is 
      poor (around sqrt r). the improvement is in the logarithmic and 
      constant terms. arguably also the algorithm here is simpler to implement 
      (compared to SVT technology). also the proof is simpler. I didn't 
      check (in the appendix) whether the claim of improvement from log(n) to 
      log(r) is correct, but I couldn't think of a counter example for this 
      either. the paper also presents an algorithm and analysis for 
      noisy matrix reconstruction, for matrices that are sum of low rank and 
      gaussian. the algorithm seems to be based on adaptation of Deshpande et 
      al's approach, where columns are sampled with probability proportional 
      to their (sampled) projection onto the orthogonal candidate column 
      space. As before, in certain parameter regimes, the approach here can be 
      better in terms of error/sample size tradeoff. 
      detailed comments p 2 "exact recover" -> "exact 
      recovery" "less well known" -> "less known" p. 3 
      "One readily verifies that \langle x,y \rangle = vec(x)^Tvec(y) " 
      you didn't define \langle x,y \rangle for tensors, so there is nothing 
      to verify. are you trying to define \langle x,y \rangle here? 
      p. 5 theorem 4: are you just "adapting" the proof 
      strategy, or are you quoting the theorem from [6]? page 6 
      last paragraph before section 5 - extremely hand wavy and 
      oversimplistic. theorem 5 is a guarantee for the algorithm 
      described in the beginning of section 5. why is the algorithm not 
      written in pseudocode like algorithm 1? p. 7 "set up" --> 
      setup p. 8 figure 1 - which is SVT and which is your 
      algorithm? It would have been nice to see a specialization 
      algorithm 1 for matrices (which is the most interesting case). 
      The authors should be aware of recent work by Ailon, Chen, 
      Huan, in which the second part is on adaptive sampling for pairwise 
      clustering matrices (although the approach is completely 
      different).