• 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