General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Mat. Sb.:

Personal entry:
Save password
Forgotten password?

Mat. Sb., 2003, Volume 194, Number 6, Pages 147–160 (Mi msb747)  

This article is cited in 49 scientific papers (total in 49 papers)

Tensor approximations of matrices generated by asymptotically smooth functions

E. E. Tyrtyshnikov

Institute of Numerical Mathematics, Russian Academy of Sciences

Abstract: For a broad class of matrices (discrete analogues of typical integral operators) their approximability by a sum of direct products of matrices of smaller size is demonstrated. Estimates of the number of terms (the tensor rank) and the corresponding error are obtained. It is shown that, as a method of data compression, tensor approximations provide superlinear compression.


Full text: PDF file (275 kB)
References: PDF file   HTML file

English version:
Sbornik: Mathematics, 2003, 194:6, 941–954

Bibliographic databases:

UDC: 512.64+517.5
MSC: Primary 15A45, 15A72; Secondary 65F05, 65F30
Received: 31.10.2002

Citation: E. E. Tyrtyshnikov, “Tensor approximations of matrices generated by asymptotically smooth functions”, Mat. Sb., 194:6 (2003), 147–160; Sb. Math., 194:6 (2003), 941–954

Citation in format AMSBIB
\by E.~E.~Tyrtyshnikov
\paper Tensor approximations of matrices generated by asymptotically smooth functions
\jour Mat. Sb.
\yr 2003
\vol 194
\issue 6
\pages 147--160
\jour Sb. Math.
\yr 2003
\vol 194
\issue 6
\pages 941--954

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Ford J.M., Oseledetst I.V., Tyrtyshnikov E.E., “Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids”, Russian J. Numer. Anal. Math. Modelling, 19:2 (2004), 185–204  crossref  mathscinet  zmath  isi  elib
    2. Ford J.M., Tyrtyshnikov E.E., “Solving linear systems using wavelet compression combined with Kronecker product approximation”, Numer. Algorithms, 40:2 (2005), 125–135  crossref  mathscinet  zmath  adsnasa  isi  elib  scopus  scopus
    3. Tian Yongge, “Some rank equalities and inequalities for Kronecker products of matrices”, Linear Multilinear Algebra, 53:6 (2005), 445–454  crossref  mathscinet  zmath  isi  elib  scopus
    4. Beylkin G., Mohlenkamp M.J., “Algorithms for numerical analysis in high dimensions”, SIAM J. Sci. Comput., 26:6 (2005), 2133–2159  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    5. Gavrilyuk I.P., Hackbusch W., Khoromskij B.N., “Hierarchical tensor-product approximation to the inverse and related operators for high-dimensional elliptic problems”, Computing, 74:2 (2005), 131–157  crossref  mathscinet  zmath  isi  elib  scopus
    6. I. V. Oseledets, E. E. Tyrtyshnikov, “Approximate inversion of matrices in the process of solving a hypersingular integral equation”, Comput. Math. Math. Phys., 45:2 (2005), 302–313  mathnet  mathscinet  zmath  elib  elib
    7. Schneider R., Weber T., “Wavelets for density matrix computation in electronic structure calculation”, Appl. Numer. Math., 56:10-11 (2006), 1383–1396  crossref  mathscinet  zmath  isi  elib  scopus
    8. Hackbusch W., Khoromskij B.N., “Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. Part I. Separable approximation of multi-variate functions”, Computing, 76:3-4 (2006), 177–202  crossref  mathscinet  zmath  isi  elib  scopus
    9. Hackbusch W., Khoromskij B.N., “Low-rank Kronecker-product approximation to multi-dimensional nonlocal operators. Part II. HKT representation of certain operators”, Computing, 76:3-4 (2006), 203–225  crossref  mathscinet  zmath  isi  elib  scopus
    10. Olshevsky V., Oseledets I., Tyrtyshnikov E., “Tensor properties of multilevel Toeplitz and related matrices”, Linear Algebra Appl., 412:1 (2006), 1–21  crossref  mathscinet  zmath  isi  elib  scopus
    11. Khoromskij B.N., Khoromskaia V., “Low rank Tucker-type tensor approximation to classical potentials”, Cent. Eur. J. Math., 5:3 (2007), 523–550  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    12. Chinnamsetty S.R., Espig M., Khoromskij B.N., Hackbusch W., Flad H.-J., “Tensor product approximation with optimal rank in quantum chemistry”, J. Chem. Phys., 127:8 (2007), 084110, 14 pp.  crossref  adsnasa  isi  elib  scopus  scopus
    13. Hackbusch W., Khoromskij B.N., “Tensor-product approximation to operators and functions in high dimensions”, J. Complexity, 23:4-6 (2007), 697–714  crossref  mathscinet  zmath  isi  elib  scopus
    14. Khoromskij B.N., “Structured data-sparse approximation to high order tensors arising from the deterministic Boltzmann equation”, Math. Comp., 76:259 (2007), 1291–1315  crossref  mathscinet  zmath  adsnasa  isi  scopus
    15. Oseledets I.V., Savostianov D.V., Tyrtyshnikov E.E., “Tucker dimensionality reduction of three-dimensional arrays in linear time”, SIAM J. Matrix Anal. Appl., 30:3 (2008), 939–956  crossref  mathscinet  isi  elib  scopus  scopus
    16. Hackbusch W., Khoromskij B.N., “Tensor-product approximation to multidimensional integral operators and Green's functions”, SIAM J. Matrix Anal. Appl., 30:3 (2008), 1233–1253  crossref  mathscinet  isi  elib  scopus
    17. Flad H.-J., Khoromskij B.N., Savostyanov D.V., Tyrtyshnikov E.E., “Verification of the cross 3D algorithm on quantum chemistry data”, Russian J. Numer. Anal. Math. Modelling, 23:4 (2008), 329–344  crossref  mathscinet  zmath  isi  elib  scopus
    18. Hackbusch W., Khoromskij B.N., Tyrtyshnikov E.E., “Approximate iterations for structured matrices”, Numer. Math., 109:3 (2008), 365–383  crossref  mathscinet  zmath  isi  elib  scopus
    19. S. A. Goreinov, “On cross approximation of multi-index arrays”, Dokl. Math., 77:3 (2008), 404–406  mathnet  crossref  mathscinet  zmath  isi  elib  elib  scopus
    20. Oseledets I., “The integral operator with logarithmic kernel has only one positive eigenvalue”, Linear Algebra Appl., 428:7 (2008), 1560–1564  crossref  mathscinet  zmath  isi  elib  scopus
    21. Oseledets I.V., Tyrtyshnikov E.E., “Breaking the curse of dimensionality, or how to use SVD in many dimensions”, SIAM J. Sci. Comput., 31:5 (2009), 3744–3759  crossref  mathscinet  zmath  isi  elib  scopus
    22. Oseledets I.V., Savostyanov D.V., Tyrtyshnikov E.E., “Cross approximation in tensor electron density computations”, Numer. Linear Algebra Appl., 2009  crossref  mathscinet  isi  scopus
    23. D. V. Savostyanov, E. E. Tyrtyshnikov, “Approximate multiplication of tensor matrices based on the individual filtering of factors”, Comput. Math. Math. Phys., 49:10 (2009), 1662–1677  mathnet  crossref  isi  elib  elib
    24. Oseledets I., Tyrtyshnikov E., Zamarashkin N., “Matrix inversion cases with size-independent tensor rank estimates”, Linear Algebra Appl., 431:5-7 (2009), 558–570  crossref  mathscinet  zmath  isi  elib  scopus
    25. Tyrtyshnikov E, “Preservation of Linear Constraints in Approximation of Tensors”, Numerical Mathematics-Theory Methods and Applications, 2:4 (2009), 421–426  mathscinet  zmath  isi
    26. Oseledets I., Tyrtyshnikov E., “TT-cross approximation for multidimensional arrays”, Linear Algebra Appl., 432:1 (2010), 70–88  crossref  mathscinet  zmath  isi  elib  scopus
    27. I. V. Oseledets, “Approximation of $2^d\times2^d$ Matrices Using Tensor Decomposition”, SIAM J Matrix Anal Appl, 31:4 (2010), 2130  crossref  mathscinet  zmath  isi  scopus
    28. Schneider J., “Error estimates for two-dimensional cross approximation”, Journal of Approximation Theory, 162:9 (2010), 1685–1700  crossref  mathscinet  zmath  isi  elib  scopus
    29. Tyrtyshnikov E., “Tensor ranks for the inversion of tensor-product binomials”, Journal of Computational and Applied Mathematics, 234:11 (2010), 3170–3174  crossref  mathscinet  zmath  isi  elib  scopus
    30. O. S. Lebedeva, “Block tensor conjugate gradient-type method for Rayleigh quotient minimization in two-dimensional case”, Comput. Math. Math. Phys., 50:5 (2010), 749–765  mathnet  crossref  adsnasa  isi  elib  elib
    31. Ivan V. Oseledets, Eugene E. Tyrtyshnikov, “Algebraic Wavelet Transform via Quantics Tensor Train Decomposition”, SIAM J. Sci. Comput, 33:3 (2011), 1315  crossref  mathscinet  zmath  isi  scopus
    32. I. V. Oseledets, “Tensor-Train Decomposition”, SIAM J. Sci. Comput, 33:5 (2011), 2295  crossref  mathscinet  zmath  isi  elib  scopus
    33. Wolfgang Hackbusch, Boris N. Khoromskij, Stefan Sauter, Eugene E.  Tyrtyshnikov, “Use of tensor formats in elliptic eigenvalue problems”, Numer. Linear Algebra Appl, 2011, n/a  crossref  mathscinet  isi  scopus
    34. Dmitry Savostyanov, “QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images”, Linear Algebra and its Applications, 2011  crossref  mathscinet  isi  scopus
    35. Boris N. Khoromskij, “Tensors-structured numerical methods in scientific computing: Survey on recent advances”, Chemometrics and Intelligent Laboratory Systems, 2011  crossref  isi  scopus
    36. Khoromskij B.N., Oseledets I.V., “QTT approximation of elliptic solution operators in higher dimensions”, Russian J Numer Anal Math Modelling, 26:3 (2011), 303–322  crossref  mathscinet  zmath  isi  elib  scopus
    37. Vladimir Kazeev, Oleg Reichmann, Christoph Schwab, “Low-rank tensor structure of linear diffusion operators in the TT and QTT formats”, Linear Algebra and its Applications, 2013  crossref  mathscinet  isi  scopus
    38. S.V. Dolgov, A.P. Smirnov, E.E. Tyrtyshnikov, “Low-rank approximation in the numerical modeling of the Farley–Buneman instability in ionospheric plasma”, Journal of Computational Physics, 2014  crossref  mathscinet  isi  scopus
    39. D.V.. Savostyanov, “Quasioptimality of maximum-volume cross interpolation of tensors”, Linear Algebra and its Applications, 458 (2014), 217  crossref  mathscinet  zmath  scopus
    40. Exl L., Abert C., Mauser N.J., Schrefl T., Stimming H.P., Suess D., “Fft-Based Kronecker Product Approximation To Micromagnetic Long-Range Interactions”, Math. Models Meth. Appl. Sci., 24:9 (2014), 1877–1901  crossref  mathscinet  zmath  isi  elib  scopus
    41. Kazeev V., Khammash M., Nip M., Schwab Ch., “Direct Solution of the Chemical Master Equation Using Quantized Tensor Trains”, PLoS Comput. Biol., 10:3 (2014), e1003359  crossref  isi  elib  scopus
    42. Vladimir Kazeev, Christoph Schwab, “Tensor Approximation of Stationary Distributions of Chemical Reaction Networks”, SIAM. J. Matrix Anal. & Appl, 36:3 (2015), 1221  crossref  mathscinet  zmath  scopus
    43. Bigoni D., Engsig-Karup A.P., Marzouk Y.M., “Spectral Tensor-Train Decomposition”, SIAM J. Sci. Comput., 38:4 (2016), A2405–A2439  crossref  mathscinet  zmath  isi  scopus
    44. Etter S., “Parallel ALS Algorithm for Solving Linear Systems in the Hierarchical Tucker Representation”, SIAM J. Sci. Comput., 38:4 (2016), A2585–A2609  crossref  mathscinet  zmath  isi  scopus
    45. Breiten T., Simoncini V., Stoll M., “Low-Rank Solvers For Fractional Differential Equations”, Electron. Trans. Numer. Anal., 45 (2016), 107–132  mathscinet  zmath  isi
    46. V. Ya. Pan, “Fast matrix multiplication and its algebraic neighbourhood”, Sb. Math., 208:11 (2017), 1661–1704  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    47. Kazeev V., Oseledets I., Rakhuba M., Schwab Ch., “Qtt-Finite-Element Approximation For Multiscale Problems i: Model Problems in One Dimension”, Adv. Comput. Math., 43:2 (2017), 411–442  crossref  mathscinet  zmath  isi  elib  scopus
    48. Trefethen L.N., “Cubature, Approximation, and Isotropy in the Hypercube”, SIAM Rev., 59:3 (2017), 469–491  crossref  mathscinet  zmath  isi  scopus
    49. Kazeev V., Schwab Ch., “Quantized Tensor-Structured Finite Elements For Second-Order Elliptic PDEs in Two Dimensions”, Numer. Math., 138:1 (2018), 133–190  crossref  mathscinet  zmath  isi  scopus
  • Математический сборник - 1992–2005 Sbornik: Mathematics (from 1967)
    Number of views:
    This page:955
    Full text:261
    First page:3

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018