A direct proof for Lovett's bound on the communication complexity of low rank matrices.

Thomas Rothvoß

Published in: CoRR (2014)

Keyphrases

low rank matrices
worst case
lower bound
upper bound
low rank
state vector
feature extraction
pairwise
higher order
matrix completion