Computing sparse approximations deterministically
type: Item
instance of: scholarly article
title: Computing sparse approximations deterministically
zbMATH Open document ID: 0852.65043
DOI: 10.1016/0024-3795(94)00175-8
author: Thomas Hofmeister
author: Hanno Lefmann
published in: Linear Algebra and its Applications
publication date: 1996-12-05T00:00:00Z
review text: \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\).
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65C99
Mathematics Subject Classification ID: 62L20
zbMATH DE Number: 894232
zbMATH Keywords: sparse approximation
zbMATH Keywords: algorithm
zbMATH Keywords: polynomial time
reviewed by: W. Gander
MaRDI profile type: Publication
full work available at URL: 0024-3795(94)00175-8
OpenAlex ID: W1987138204
cites work: On sparse approximations to randomized strategies and convex combinations
cites work: Explicit Constructions of Depth-2 Majority Circuits for Comparison and Addition
cites work: Q4004078
cites work: Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
cites work: Simple strategies for large zero-sum games with applications to complexity theory
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
Wikidata QID: Q127554611
description: scientific article; zbMATH DE number 894232