#eth/cil/theory

NP Hardness

{\hat{A}}_{k} = \arg min {\sum_{i, j} (w_{i, j} a_{i j} - b_{i j})^{2}}, rank (B) = k

special case: $w_{i j} = w_{i j} \in {0, 1}$ , ?!!? maybe $w_{i j} = w_{j i}$
This is NP-hard even for $k = 1$

Low rank matrix reconstruction is NP hard and one has - in general - to resort to approximation algorithms. The completely observed case is special.

Connected Pages

Depth

On this page

Pages mentioning this page

cil-theory-overview

03-00-singular-value-decomposition