Computing sparse approximations deterministically (Q1915603): Difference between revisions

\textit{I. Althöfer} [ibid. 199, 339-355 (1994; Zbl 0801.90074)] proved that for an \(m \times n\) matrix \(A\) with elements in \([0,1]\) and for every probability vector \(p\) there exists a sparse probability vector \(q\) with \(O ((\ln n)/ \varepsilon^2)\) nonzero entries such that every component of \(Ap\) differs from \(Aq\) in absolute value at most by \(\varepsilon\). The authors present an algorithm to compute \(q\) which takes polynomial time in \(n,m\) and \(1/ \varepsilon\).