{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T18:11:20Z","timestamp":1787595080842,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>The Fourier transform of a continuous function, evaluated at frequencies expressed in polar coordinates, is an important conceptual tool for understanding physical continuum phenomena. An analogous tool, suitable for computations on discrete grids, could be very useful; however, no exact analogue exists in the discrete case. In this paper we present the notion of pseudopolar grid (pp grid) and the pseudopolar Fourier transform (ppFT), which evaluates the discrete Fourier transform at points of the pp grid. The pp grid is a type of concentric-squares grid in which the radial density of squares is twice as high as usual. The pp grid consists of equally spaced samples along rays, where different rays are equally spaced in slope rather than angle. We develop a fast algorithm for the ppFT, with the same complexity order as the Cartesian fast Fourier transform; the algorithm is stable, invertible, requires only one-dimensional operations, and uses no approximate interpolations. We prove that the ppFT is invertible and develop two algorithms for its inversion: iterative and direct, both with complexity $O(n^{2}\\log{n})$, where $n \\times n$ is the size of the reconstructed image. The iterative algorithm applies conjugate gradients to the Gram operator of the ppFT. Since the transform is ill-conditioned, we introduce a preconditioner, which significantly accelerates the convergence. The direct inversion algorithm utilizes the special frequency domain structure of the transform in two steps. First, it resamples the pp grid to a Cartesian frequency grid and then recovers the image from the Cartesian frequency grid.<\/jats:p>","DOI":"10.1137\/060650283","type":"journal-article","created":{"date-parts":[[2008,2,14]],"date-time":"2008-02-14T11:55:06Z","timestamp":1202990106000},"page":"764-784","source":"Crossref","is-referenced-by-count":77,"title":["A Framework for Discrete Integral Transformations I\u2014The Pseudopolar Fourier Transform"],"prefix":"10.1137","volume":"30","author":[{"given":"A.","family":"Averbuch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R. R.","family":"Coifman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D. L.","family":"Donoho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Israeli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Y.","family":"Shkolnisky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,2,14]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850056"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2005.11.003"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/060650301"},{"key":"R4","unstructured":"A. Averbuch, R. R. Coifman, D. L. Donoho, M. Israeli, J. Wald\u00e9n, and Y. Shkolnisky,\n                      Fast Slant Stack: A Notion of Radon Transform for Data in a Cartesian Grid which is Rapidly Computible, Algebraically Exact, Geometrically Faithful and Invertible\n                      , manuscript, 2001."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/1033097"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/05064182X"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1965-0178586-1"},{"key":"R8","unstructured":"D. L. Donoho and A. G. Flesia,\n                      Digital ridgelet transform based on true ridge functions\n                      , in Beyond Wavelets, Vol. 10, J. Stoecker and G. V. Welland, eds., Academic Press, New York, 2003."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"D. L. Donoho and O. Levi,\n                      Fast x-ray and beamlet transforms for three-dimensional data\n                      , in Modern Signal Processing, Math. Sci. Res. Inst. Publ. 46, D. M. Healy and D. Rockmore, eds., Cambridge University Press, Cambridge, UK, 2004, pp. 79\u2013116.","DOI":"10.1017\/9781009701297.004"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/acha.1995.1007"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.1987.4307847"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/42.7788"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050101"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-003-0021-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1021"},{"key":"R16","first-page":"201","volume":"7","author":"Gohberg I.","year":"1972","journal-title":"Mat. Issled.","ISSN":"https:\/\/id.crossref.org\/issn\/0542-9994","issn-type":"print"},{"key":"R17","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , The Johns Hopkins University Press, Baltimore, MD, 1984."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Greenbaum,\n                      Iterative Methods for Solving Linear Systems\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611970937"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450343200X"},{"key":"R20","unstructured":"http:\/\/curvelet.org\/."},{"key":"R21","unstructured":"http:\/\/www-stat.stanford.edu\/~beamlab\/."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"T. Kailath and A. H. Sayed, eds.\n                      Fast Reliable Algorithms for Matrices with Structure\n                      , SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9781611971354"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2006.875227"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2005.128"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/29.1609"},{"key":"R26","unstructured":"O. Levi,\n                      Multiscale Geometric Analysis of Three-Dimensional Data\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 2005."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02248694"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"M. Lustig, J. Tsaig, J. H. Lee, and D. Donoho,\n                      Fast spiral Fourier transform for iterative MR image reconstruction\n                      , in Proceedings of the IEEE International Symposium on Biomedical Imaging: Nano to Macro, Arlington, VA, 2004, pp. 784\u2013787.","DOI":"10.1109\/ISBI.2004.1398655"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1974.9625"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"F. Natterer,\n                      The Mathematics of Computerized Tomography\n                      , Classics Appl. Math. 32, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898719284"},{"key":"R31","unstructured":"J. E. Pasciak,\n                      A Note on the Fourier Algorithm for Image Reconstruction\n                      , preprint, Applied Mathematics Department, Brookhaven National Laboratory, Upton, NY, 1973."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/21.3.769"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1109\/TAU.1969.1162034"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2002.1014998"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/S003614459731533X"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060650283","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:56:05Z","timestamp":1787334965000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060650283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060650283"],"URL":"https:\/\/doi.org\/10.1137\/060650283","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}