{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T15:56:58Z","timestamp":1783526218660,"version":"3.55.0"},"reference-count":0,"publisher":"Walter de Gruyter GmbH","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We propose a superfast discrete Haar wavelet transform (SFHWT) as\nwell as its inverse, using the low-rank Quantics-TT (QTT) representation for\nthe Haar transform matrices and input-output vectors. Though the Haar matrix\nitself does not have a low QTT rank approximation, we show that factor matrices\nused at each step of the traditional multilevel Haar wavelet transform\nalgorithm have explicit QTT representations of low rank.\nThe SFHWT applies to a vector representing a signal sampled on a uniform grid\nof size <jats:inline-formula id=\"eq1_w2aab2b8b3b1b7b1aab1c13b1b1Aa\">\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/cmam-2014-0016_98215ed0bec2047ed2f5f5b99c723c78.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mrow>\n                              <m:mi>N<\/m:mi>\n                              <m:mo>=<\/m:mo>\n                              <m:msup>\n                                 <m:mn>2<\/m:mn>\n                                 <m:mi>d<\/m:mi>\n                              <\/m:msup>\n                           <\/m:mrow>\n                        <\/m:math>\n                        <jats:tex-math>${N=2^d}$<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula>. We develop two algorithms which roughly require square\nlogarithmic time complexity <jats:inline-formula id=\"eq2_w2aab2b8b3b1b7b1aab1c13b1b3Aa\">\n                     <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/cmam-2014-0016_f530572c1e0b30ee9cadda70c5494104.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                           <m:mrow>\n                              <m:mi>O<\/m:mi>\n                              <m:mo>(<\/m:mo>\n                              <m:msup>\n                                 <m:mo form=\"prefix\">log<\/m:mo>\n                                 <m:mn>2<\/m:mn>\n                              <\/m:msup>\n                              <m:mi>N<\/m:mi>\n                              <m:mo>)<\/m:mo>\n                           <\/m:mrow>\n                        <\/m:math>\n                        <jats:tex-math>${O(\\log ^2 N)}$<\/jats:tex-math>\n                     <\/jats:alternatives>\n                  <\/jats:inline-formula> with respect to the grid size,\nhence outperforming the traditional fast Haar wavelet transform (FHWT) of\nlinear complexity <jats:italic>O<\/jats:italic>(<jats:italic>N<\/jats:italic>). Our approach also applies to the FHWT inverse as\nwell as to the multidimensional wavelet transform. Numerical experiments\ndemonstrate that the SFHWT algorithm is robust in keeping low rank of the\nresulting output vector and it outperforms the traditional FHWT for grid sizes\nlarger than a certain value depending on the spacial dimension.<\/jats:p>","DOI":"10.1515\/cmam-2014-0016","type":"journal-article","created":{"date-parts":[[2014,6,12]],"date-time":"2014-06-12T20:20:06Z","timestamp":1402604406000},"page":"537-553","source":"Crossref","is-referenced-by-count":4,"title":["Superfast Wavelet Transform Using Quantics-TT\nApproximation. I. Application to Haar Wavelets"],"prefix":"10.1515","volume":"14","author":[{"given":"Boris N.","family":"Khoromskij","sequence":"first","affiliation":[{"name":"Max-Planck-Institute for Mathematics in the Sciences, Inselstr. 22\u201326, 04103 Leipzig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sentao","family":"Miao","sequence":"additional","affiliation":[{"name":"School of Engineering & Science (SES), Jacobs University, Campus Ring 1, 28759 Bremen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"374","published-online":{"date-parts":[[2014,6,12]]},"container-title":["Computational Methods in Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/cmam\/14\/4\/article-p537.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2014-0016\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2014-0016\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,31]],"date-time":"2023-03-31T21:02:35Z","timestamp":1680296555000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/cmam-2014-0016\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,12]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2014,8,20]]},"published-print":{"date-parts":[[2014,10,1]]}},"alternative-id":["10.1515\/cmam-2014-0016"],"URL":"https:\/\/doi.org\/10.1515\/cmam-2014-0016","relation":{},"ISSN":["1609-4840","1609-9389"],"issn-type":[{"value":"1609-4840","type":"print"},{"value":"1609-9389","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,12]]}}}