Name
Abstract | ||
|---|---|---|
In spite of an extensive literature on fast algorithms for synthetic aperture radar (SAR) imaging, it is not currently known if it is possible to accurately form an image from $N$ data points in provable near-linear time complexity. This paper seeks to close this gap by proposing an algorithm which runs in complexity $O(N \log N \log(1/\epsilon))$ without making the far-field approximation or imposing the beam pattern approximation required by time-domain backprojection, with $\epsilon$ the desired pixelwise accuracy. It is based on the butterfly scheme, which unlike the FFT works for vastly more general oscillatory integrals than the discrete Fourier transform. A complete error analysis is provided: the rigorous complexity bound has additional powers of $\log N$ and $\log(1/\epsilon)$ that are not observed in practice. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/100811593 | Siam Journal on Control and Optimization |
Keywords | Field | DocType |
butterfly scheme,provable near-linear time complexity,discrete fourier,extensive literature,beam pattern approximation,complete error analysis,data point,far-field approximation,rigorous complexity,butterfly algorithm,synthetic aperture radar imaging,additional power,synthetic aperture radar | Data point,Binary logarithm,Mathematical optimization,Synthetic aperture radar imaging,Synthetic aperture radar,Algorithm,Fast Fourier transform,Beam pattern,Discrete Fourier transform,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 1 | 1936-4954 |
Citations | PageRank | References |
6 | 0.55 | 8 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Demanet | 1 | 750 | 57.81 |
| Matthew Ferrara | 2 | 24 | 3.35 |
| Nicholas Maxwell | 3 | 6 | 0.88 |
| Jack Poulson | 4 | 138 | 8.85 |
| Lexing Ying | 5 | 1273 | 103.92 |