Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOW-RANK APPROXIMATION:
Reports tagged with Low-rank approximation:
TR12-169 | 22nd November 2012
Noga Alon, Santosh Vempala

#### The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any  \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>>

TR18-103 | 30th April 2018
Zhao Song, David Woodruff, Peilin Zhong

#### Relative Error Tensor Low Rank Approximation

We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$ tensor $A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where ${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>>

ISSN 1433-8092 | Imprint