Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with low-rank matrix approximation:
TR06-042 | 16th March 2006
Amit Deshpande, Santosh Vempala

Adaptive Sampling and Fast Low-Rank Matrix Approximation

We prove that any real matrix $A$ contains a subset of at most
$4k/\eps + 2k \log(k+1)$ rows whose span ``contains" a matrix of
rank at most $k$ with error only $(1+\eps)$ times the error of the
best rank-$k$ approximation of $A$. This leads to an algorithm to
find such ... more >>>

TR11-066 | 25th April 2011
Venkatesan Guruswami, Ali Kemal Sinop

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

TR18-128 | 11th July 2018
Ewin Tang

A quantum-inspired classical algorithm for recommendation systems

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an $m\times n$ matrix of small rank $k$. We give the first classical algorithm to produce a recommendation in $O(\text{poly}(k)\text{polylog}(m,n))$ time, which is an exponential improvement on previous ... more >>>

ISSN 1433-8092 | Imprint