DocumentCode
2042399
Title
On sparse representations of linear operators and the approximation of matrix products
Author
Belabbas, Mohamed-Ali ; Wolfe, Patrick J.
Author_Institution
Dept. of Stat., Harvard Univ., Cambridge, MA
fYear
2008
fDate
19-21 March 2008
Firstpage
258
Lastpage
263
Abstract
Thus far, sparse representations have been exploited largely in the context of robustly estimating functions in a noisy environment from a few measurements. In this context, the existence of a basis in which the signal class under consideration is sparse is used to decrease the number of necessary measurements while controlling the approximation error. In this paper, we instead focus on applications in numerical analysis, by way of sparse representations of linear operators with the objective of minimizing the number of operations needed to perform basic operations (here, multiplication) on these operators. We represent a linear operator by a sum of rank-one operators, and show how a sparse representation that guarantees a low approximation error for the product can be obtained from analyzing an induced quadratic form. This construction in turn yields new algorithms for computing approximate matrix products.
Keywords
approximation theory; mathematical operators; sparse matrices; linear operators; matrix products approximation; rank-one operators; sparse representations; Approximation error; Constraint optimization; Kernel; Linear algebra; Matrix decomposition; Numerical analysis; Robustness; Sampling methods; Sparse matrices; Working environment noise;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Sciences and Systems, 2008. CISS 2008. 42nd Annual Conference on
Conference_Location
Princeton, NJ
Print_ISBN
978-1-4244-2246-3
Electronic_ISBN
978-1-4244-2247-0
Type
conf
DOI
10.1109/CISS.2008.4558532
Filename
4558532
Link To Document