47:(FFT) plays an indispensable role on many scientific domains, especially on signal processing. It is one of the top-10 algorithms in the twentieth century. However, with the advent of big data era, the FFT still needs to be improved in order to save more computing power. Recently, the sparse Fourier transform (SFT) has gained a considerable amount of attention, for it performs well on analyzing the long sequence of data with few signal components.
659:
911:
816:
603:
373:
1205:
900:
1079:
By randomly bining frequencies, all components can be separated. Then, taking them into filter banks, so each band only contains a single frequency. It is convenient to use the methods we mentioned to recover this signal frequency.
1321:
212:
709:
454:
1031:
426:
436:
Assume only a single frequency exists in the sequence. In order to recover this frequency from the sequence, it is reasonable to utilize the relationship between adjacent points of the sequence.
1545:
648:
1455:
1390:
232:
1637:
1590:
701:
1951:; M. Strauss (21 September 2005). "Improved time bounds for near-optimal sparse Fourier representations". In Papadakis, Manos; Laine, Andrew F; Unser, Michael A (eds.).
1990:
Ghazi, Badih; Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric; Lixin Shi (2013). "Sample-optimal average-case sparse
Fourier Transform in two dimensions".
827:
1475:
1094:
1063:
can separate all frequencies, including
Gaussians, indicator functions, spike trains, and Dolph-Chebyshev filters. Each bank only contains a single frequency.
1639:
and requires nearly linear time decoding time. A dimension-incremental algorithm was proposed by Potts, Volkmer based on sampling along rank-1 lattices.
2129:
Pawar, Sameer; Ramchandran, Kannan (2013). "Computing a k-sparse n-length
Discrete Fourier Transform using at most 4k samples and O(k log k) complexity".
87:
918:
Now, we desire to explore the case of multiple frequencies, instead of a single frequency. The adjacent frequencies can be separated by the scaling
2310:
Nakos, Vasileios; Song, Zhao; Wang, Zhengyu (2019). "(Nearly) Sample-Optimal Sparse
Fourier Transform in Any Dimension; RIPless and Filterless".
811:{\displaystyle k=104{,}134\equiv \left\{{\begin{array}{rl}34&{\bmod {1}}00,\\3&{\bmod {1}}01,\\1&{\bmod {1}}03.\end{array}}\right.}
598:{\displaystyle {\frac {x_{n+1}}{x_{n}}}=e^{j{\frac {2\pi }{N}}k}=\cos \left({\frac {2\pi k}{N}}\right)+j\sin \left({\frac {2\pi k}{N}}\right).}
2146:
2017:
1948:
1907:
1886:
1712:
1221:
2257:
Kapralov, Michael (2016). "Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time".
944:
2286:
2204:
1088:
After identifying frequencies, we will have many frequency components. We can use
Fourier transform to estimate their coefficients.
1923:
381:
1056:
703:
for an example. Now, we have three relatively prime integers 100, 101, and 103. Thus, the equation can be described as
37:
1480:
938:
reveals by randomly binning frequencies, we can utilize the single frequency recovery to seek the main components.
25:
2422:
1660:
671:
611:
1748:
368:{\displaystyle X_{k}={\frac {1}{N}}(Fx)_{k}={\frac {1}{N}}\sum _{n=0}^{N-1}x_{n}e^{-j{\frac {2\pi }{N}}kn}.}
1403:
1215:
Finally, repeating these two stages can we extract the most important components from the original signal.
44:
1334:
1595:
2335:
Potts, Daniel; Volkmer, Toni (2016). "Sparse high-dimensional FFT based on rank-1 lattice sampling".
2076:
Mark A.Iwen (2013-01-01). "Improved approximation guarantees for sublinear-time
Fourier algorithms".
1956:
1763:
1550:
1749:"Recent Developments in the Sparse Fourier Transform: A compressed Fourier transform for big data"
2396:
2367:
2315:
2292:
2264:
2237:
2210:
2182:
2152:
2111:
2085:
2058:
2023:
1995:
1972:
1929:
1843:
1789:
680:
2362:
Price, Eric; Song, Zhao (2015). "A Robust Sparse
Fourier Transform in the Continuous Setting".
1592:. In 2019, Nakos, Song, and Wang introduced a new algorithm which uses nearly optimal samples
2427:
2282:
2200:
2142:
2103:
2013:
1919:
1882:
1708:
1647:
There are several works about generalizing the discrete setting into the continuous setting.
895:{\displaystyle k=104{,}134{\bmod {(}}100\cdot 101\cdot 103)=104{,}134{\bmod {1}}{,}040{,}300}
2344:
2274:
2192:
2134:
2095:
2050:
2005:
1964:
1911:
1874:
1866:
1835:
1779:
1771:
1200:{\displaystyle X_{k}'={\frac {1}{L}}\sum _{l=1}^{L}x_{n}'e^{-j{\frac {2\pi }{N}}n'\ell }}
1992:
2013 51st Annual
Allerton Conference on Communication, Control, and Computing (Allerton)
1960:
1807:
Cipra, Barry A. (2000). "The best of the 20th century: Editors name top 10 algorithms".
1767:
1460:
934:, the distribution of all frequencies can be almost a uniform distribution. The figure
69:
65:
658:
2416:
2296:
2115:
1976:
1933:
1793:
1671:
2214:
2062:
2027:
1847:
207:{\displaystyle x_{n}=(F^{*}X)_{n}=\sum _{k=0}^{N-1}X_{k}e^{j{\frac {2\pi }{N}}kn}.}
2156:
2009:
1902:
A. C. Gilbert (2002). "Near-optimal sparse fourier representations via sampling".
448:
can be obtained by dividing the adjacent points of the sequence. In other words,
1691:
1060:
2388:
2348:
2258:
2099:
1870:
1331:
In 2012, Hassanieh, Indyk, Katabi, and Price proposed an algorithm that takes
730:
2229:
2138:
2054:
1839:
910:
2174:
2107:
2041:
Iwen, M. A. (2010-01-05). "Combinatorial
Sublinear-Time Fourier Algorithms".
1826:
Iwen, M. A. (2010-01-05). "Combinatorial
Sublinear-Time Fourier Algorithms".
1775:
2278:
2196:
2260:
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
2179:
Proceedings of the forty-fourth annual ACM symposium on Theory of computing
1904:
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
1681:
1676:
1915:
1784:
29:
1878:
1477:. In 2016, Kapralov proposed an algorithm that uses sublinear samples
1968:
1686:
1316:{\displaystyle x_{n}-\sum _{k'=1}^{k}X_{k}'e^{j{\frac {2\pi }{N}}k'n}}
1667:
and Universtity of Technology Chemnitz . Also, they are free online.
2173:
Hassanieh, Haitham; Indyk, Piotr; Katabi, Dina; Price, Eric (2012).
1747:
Gilbert, Anna C.; Indyk, Piotr; Iwen, Mark; Schmidt, Ludwig (2014).
2401:
2372:
2320:
2269:
2242:
2187:
2090:
2000:
909:
657:
1707:. Association for Computing Machinery and Morgan & Claypool.
1861:
Haitham Hassanieh; Piotr Indyk; Dina Katabi; Eric Price (2012).
1026:{\displaystyle x_{n}'=X_{k}e^{j{\frac {2\pi }{N}}(c\cdot k+b)},}
1664:
1656:
1400:
In 2014, Indyk and Kapralov proposed an algorithm that takes
33:
875:
841:
789:
764:
739:
2387:
Chen, Xue; Kane, Daniel M.; Price, Eric; Song, Zhao (2016).
2230:"Sample-optimal Fourier sampling in any constant dimension"
1863:
Simple and Practical Algorithm for Sparse Fourier Transform
926:
properties. Namely, by randomly choosing the parameters of
805:
1955:. Proceedings of SPIE. Vol. 5914. pp. 59141A.
1396:
Sparse Fourier transform in the high dimensional setting
2131:
2013 IEEE International Symposium on Information Theory
2389:"Fourier-Sparse Interpolation without a Frequency Gap"
421:{\displaystyle F:\mathbb {C} ^{N}\to \mathbb {C} ^{N}}
1598:
1553:
1483:
1463:
1406:
1337:
1224:
1097:
947:
830:
712:
683:
614:
457:
384:
235:
90:
2393:
Annual Symposium on Foundations of Computer Science
2364:
Annual Symposium on Foundations of Computer Science
2312:
Annual Symposium on Foundations of Computer Science
2234:
Annual Symposium on Foundations of Computer Science
1643:Sparse Fourier transform in the continuous setting
1631:
1584:
1539:
1469:
1449:
1384:
1315:
1199:
1025:
894:
810:
695:
642:
597:
420:
367:
206:
1705:The Sparse Fourier Transform: Theory and Practice
1327:Sparse Fourier transform in the discrete setting
378:Hence, from the equations above, the mapping is
1540:{\displaystyle 2^{O(d^{2})}k\log n\log \log n}
2168:
2166:
8:
1071:Generally, all SFT follows the three stages
2337:Applied and Computational Harmonic Analysis
2078:Applied and Computational Harmonic Analysis
1392:samples and runs in the same running time.
1457:samples and runs in nearly linear time in
2400:
2371:
2319:
2268:
2241:
2186:
2175:"Nearly optimal sparse fourier transform"
2089:
1999:
1783:
1597:
1561:
1552:
1499:
1488:
1482:
1462:
1411:
1405:
1368:
1336:
1285:
1281:
1268:
1258:
1242:
1229:
1223:
1169:
1162:
1149:
1139:
1128:
1114:
1102:
1096:
982:
978:
968:
952:
946:
884:
878:
874:
844:
840:
829:
792:
788:
767:
763:
742:
738:
729:
711:
682:
643:{\displaystyle x_{n}\in \mathbb {C} ^{N}}
634:
630:
629:
619:
613:
570:
532:
499:
495:
480:
464:
458:
456:
412:
408:
407:
397:
393:
392:
383:
339:
332:
322:
306:
295:
281:
272:
249:
240:
234:
178:
174:
164:
148:
137:
124:
111:
95:
89:
2228:Indyk, Piotr; Kapralov, Michael (2014).
2043:Foundations of Computational Mathematics
1828:Foundations of Computational Mathematics
1055:, the whole spectrum can be looked like
1736:
1742:
1740:
36:synchronization, spectrum sensing and
1450:{\displaystyle 2^{O(d\log d)}k\log n}
32:signals. Specifically, it is used in
7:
1724:Sparse Recovery and Fourier Sampling
1385:{\displaystyle O(k\log n\log(n/k))}
2181:. STOC'12. ACM. pp. 563–578.
14:
1655:There are several works based on
1910:, M. Strauss. pp. 152–161.
1632:{\displaystyle O(k\log n\log k)}
1756:IEEE Signal Processing Magazine
1626:
1602:
1585:{\displaystyle k\log ^{O(d)}n}
1571:
1565:
1505:
1492:
1430:
1415:
1379:
1376:
1362:
1341:
1015:
997:
865:
845:
403:
269:
259:
121:
104:
1:
2263:. STOC'16. pp. 264–277.
2010:10.1109/Allerton.2013.6736670
1547:and sublinear decoding time
906:Randomly binning frequencies
38:analog-to-digital converters
1703:Hassanieh, Haitham (2018).
696:{\displaystyle k=104{,}134}
2444:
2349:10.1016/j.acha.2015.05.002
2100:10.1016/j.acha.2012.03.007
1871:10.1137/1.9781611973099.93
26:discrete Fourier transform
2139:10.1109/ISIT.2013.6620269
2055:10.1007/s10208-009-9057-1
1840:10.1007/s10208-009-9057-1
1059:. Then, taking them into
672:Chinese remainder theorem
432:Single frequency recovery
1776:10.1109/MSP.2014.2329131
1044:is modulation property.
1040:is scaling property and
662:An aliasing-based search
654:An aliasing-based search
18:sparse Fourier transform
2279:10.1145/2897518.2897650
2197:10.1145/2213977.2214029
1084:Estimating coefficients
1075:Identifying frequencies
1994:. pp. 1258–1265.
1865:. pp. 1183–1194.
1633:
1586:
1541:
1471:
1451:
1386:
1317:
1263:
1201:
1144:
1027:
936:Spread all frequencies
915:
914:Spread all frequencies
896:
812:
697:
663:
644:
599:
422:
369:
317:
226:can be represented as
208:
159:
45:fast Fourier transform
1916:10.1145/509907.509933
1906:. S. Guha, P. Indyk,
1634:
1587:
1542:
1472:
1452:
1387:
1318:
1238:
1202:
1124:
1047:By randomly choosing
1028:
913:
897:
813:
698:
661:
645:
600:
423:
370:
291:
209:
133:
2395:. FOCS'16: 741–750.
2366:. FOCS'15: 583–600.
2236:. FOCS'14: 514–523.
2133:. pp. 464–468.
1722:Price, Eric (2013).
1596:
1551:
1481:
1461:
1404:
1335:
1222:
1095:
1067:The prototypical SFT
1057:uniform distribution
945:
828:
710:
681:
612:
455:
382:
233:
88:
55:Consider a sequence
1961:2005SPIE.5914..398G
1768:2014ISPM...31...91G
1692:TUC implementations
1682:MIT implementations
1677:ETH implementations
1672:MSU implementations
1276:
1157:
1110:
960:
28:(DFT) for handling
1629:
1582:
1537:
1467:
1447:
1382:
1313:
1264:
1197:
1145:
1098:
1023:
948:
916:
892:
808:
803:
693:
664:
640:
595:
418:
365:
204:
81:can be written as
2148:978-1-4799-0446-4
2019:978-1-4799-3410-2
1969:10.1117/12.615931
1888:978-1-61197-210-8
1714:978-1-94748-707-9
1470:{\displaystyle n}
1298:
1182:
1122:
995:
586:
548:
512:
486:
352:
289:
257:
191:
2435:
2423:Fourier analysis
2407:
2406:
2404:
2384:
2378:
2377:
2375:
2359:
2353:
2352:
2332:
2326:
2325:
2323:
2307:
2301:
2300:
2272:
2254:
2248:
2247:
2245:
2225:
2219:
2218:
2190:
2170:
2161:
2160:
2126:
2120:
2119:
2093:
2073:
2067:
2066:
2038:
2032:
2031:
2003:
1987:
1981:
1980:
1949:S. Muthukrishnan
1944:
1938:
1937:
1908:S. Muthukrishnan
1899:
1893:
1892:
1858:
1852:
1851:
1823:
1817:
1816:
1804:
1798:
1797:
1787:
1753:
1744:
1727:
1718:
1638:
1636:
1635:
1630:
1591:
1589:
1588:
1583:
1575:
1574:
1546:
1544:
1543:
1538:
1509:
1508:
1504:
1503:
1476:
1474:
1473:
1468:
1456:
1454:
1453:
1448:
1434:
1433:
1391:
1389:
1388:
1383:
1372:
1322:
1320:
1319:
1314:
1312:
1311:
1307:
1299:
1294:
1286:
1272:
1262:
1257:
1250:
1234:
1233:
1206:
1204:
1203:
1198:
1196:
1195:
1191:
1183:
1178:
1170:
1153:
1143:
1138:
1123:
1115:
1106:
1032:
1030:
1029:
1024:
1019:
1018:
996:
991:
983:
973:
972:
956:
901:
899:
898:
893:
888:
883:
882:
849:
848:
821:By CRT, we have
817:
815:
814:
809:
807:
804:
797:
796:
772:
771:
747:
746:
702:
700:
699:
694:
649:
647:
646:
641:
639:
638:
633:
624:
623:
604:
602:
601:
596:
591:
587:
582:
571:
553:
549:
544:
533:
518:
517:
513:
508:
500:
487:
485:
484:
475:
474:
459:
427:
425:
424:
419:
417:
416:
411:
402:
401:
396:
374:
372:
371:
366:
361:
360:
353:
348:
340:
327:
326:
316:
305:
290:
282:
277:
276:
258:
250:
245:
244:
213:
211:
210:
205:
200:
199:
192:
187:
179:
169:
168:
158:
147:
129:
128:
116:
115:
100:
99:
2443:
2442:
2438:
2437:
2436:
2434:
2433:
2432:
2413:
2412:
2411:
2410:
2386:
2385:
2381:
2361:
2360:
2356:
2334:
2333:
2329:
2309:
2308:
2304:
2289:
2256:
2255:
2251:
2227:
2226:
2222:
2207:
2172:
2171:
2164:
2149:
2128:
2127:
2123:
2075:
2074:
2070:
2040:
2039:
2035:
2020:
1989:
1988:
1984:
1947:A. C. Gilbert;
1946:
1945:
1941:
1926:
1901:
1900:
1896:
1889:
1860:
1859:
1855:
1825:
1824:
1820:
1806:
1805:
1801:
1751:
1746:
1745:
1738:
1733:
1721:
1715:
1702:
1700:
1698:Further reading
1653:
1651:Implementations
1645:
1594:
1593:
1557:
1549:
1548:
1495:
1484:
1479:
1478:
1459:
1458:
1407:
1402:
1401:
1398:
1333:
1332:
1329:
1300:
1287:
1277:
1243:
1225:
1220:
1219:
1213:
1184:
1171:
1158:
1093:
1092:
1086:
1077:
1069:
984:
974:
964:
943:
942:
922:and modulation
908:
826:
825:
802:
801:
786:
780:
779:
761:
755:
754:
736:
725:
708:
707:
679:
678:
670:can be done by
656:
628:
615:
610:
609:
572:
566:
534:
528:
501:
491:
476:
460:
453:
452:
442:
434:
406:
391:
380:
379:
341:
328:
318:
268:
236:
231:
230:
225:
180:
170:
160:
120:
107:
91:
86:
85:
80:
66:complex numbers
63:
53:
24:) is a kind of
12:
11:
5:
2441:
2439:
2431:
2430:
2425:
2415:
2414:
2409:
2408:
2379:
2354:
2343:(3): 713–748.
2327:
2302:
2287:
2249:
2220:
2205:
2162:
2147:
2121:
2068:
2049:(3): 303–338.
2033:
2018:
1982:
1939:
1924:
1894:
1887:
1853:
1834:(3): 303–338.
1818:
1799:
1735:
1734:
1732:
1729:
1713:
1699:
1696:
1695:
1694:
1689:
1684:
1679:
1674:
1652:
1649:
1644:
1641:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1581:
1578:
1573:
1570:
1567:
1564:
1560:
1556:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1507:
1502:
1498:
1494:
1491:
1487:
1466:
1446:
1443:
1440:
1437:
1432:
1429:
1426:
1423:
1420:
1417:
1414:
1410:
1397:
1394:
1381:
1378:
1375:
1371:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1328:
1325:
1324:
1323:
1310:
1306:
1303:
1297:
1293:
1290:
1284:
1280:
1275:
1271:
1267:
1261:
1256:
1253:
1249:
1246:
1241:
1237:
1232:
1228:
1212:
1209:
1208:
1207:
1194:
1190:
1187:
1181:
1177:
1174:
1168:
1165:
1161:
1156:
1152:
1148:
1142:
1137:
1134:
1131:
1127:
1121:
1118:
1113:
1109:
1105:
1101:
1085:
1082:
1076:
1073:
1068:
1065:
1034:
1033:
1022:
1017:
1014:
1011:
1008:
1005:
1002:
999:
994:
990:
987:
981:
977:
971:
967:
963:
959:
955:
951:
907:
904:
903:
902:
891:
887:
881:
877:
873:
870:
867:
864:
861:
858:
855:
852:
847:
843:
839:
836:
833:
819:
818:
806:
800:
795:
791:
787:
785:
782:
781:
778:
775:
770:
766:
762:
760:
757:
756:
753:
750:
745:
741:
737:
735:
732:
731:
728:
724:
721:
718:
715:
692:
689:
686:
666:Seeking phase
655:
652:
637:
632:
627:
622:
618:
606:
605:
594:
590:
585:
581:
578:
575:
569:
565:
562:
559:
556:
552:
547:
543:
540:
537:
531:
527:
524:
521:
516:
511:
507:
504:
498:
494:
490:
483:
479:
473:
470:
467:
463:
441:
440:Phase encoding
438:
433:
430:
415:
410:
405:
400:
395:
390:
387:
376:
375:
364:
359:
356:
351:
347:
344:
338:
335:
331:
325:
321:
315:
312:
309:
304:
301:
298:
294:
288:
285:
280:
275:
271:
267:
264:
261:
256:
253:
248:
243:
239:
221:
215:
214:
203:
198:
195:
190:
186:
183:
177:
173:
167:
163:
157:
154:
151:
146:
143:
140:
136:
132:
127:
123:
119:
114:
110:
106:
103:
98:
94:
76:
70:Fourier series
59:
52:
49:
13:
10:
9:
6:
4:
3:
2:
2440:
2429:
2426:
2424:
2421:
2420:
2418:
2403:
2398:
2394:
2390:
2383:
2380:
2374:
2369:
2365:
2358:
2355:
2350:
2346:
2342:
2338:
2331:
2328:
2322:
2317:
2313:
2306:
2303:
2298:
2294:
2290:
2288:9781450341325
2284:
2280:
2276:
2271:
2266:
2262:
2261:
2253:
2250:
2244:
2239:
2235:
2231:
2224:
2221:
2216:
2212:
2208:
2206:9781450312455
2202:
2198:
2194:
2189:
2184:
2180:
2176:
2169:
2167:
2163:
2158:
2154:
2150:
2144:
2140:
2136:
2132:
2125:
2122:
2117:
2113:
2109:
2105:
2101:
2097:
2092:
2087:
2083:
2079:
2072:
2069:
2064:
2060:
2056:
2052:
2048:
2044:
2037:
2034:
2029:
2025:
2021:
2015:
2011:
2007:
2002:
1997:
1993:
1986:
1983:
1978:
1974:
1970:
1966:
1962:
1958:
1954:
1950:
1943:
1940:
1935:
1931:
1927:
1921:
1917:
1913:
1909:
1905:
1898:
1895:
1890:
1884:
1880:
1876:
1872:
1868:
1864:
1857:
1854:
1849:
1845:
1841:
1837:
1833:
1829:
1822:
1819:
1814:
1810:
1803:
1800:
1795:
1791:
1786:
1785:1721.1/113828
1781:
1777:
1773:
1769:
1765:
1762:(5): 91–100.
1761:
1757:
1750:
1743:
1741:
1737:
1730:
1728:
1725:
1719:
1716:
1710:
1706:
1697:
1693:
1690:
1688:
1685:
1683:
1680:
1678:
1675:
1673:
1670:
1669:
1668:
1666:
1662:
1658:
1650:
1648:
1642:
1640:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1599:
1579:
1576:
1568:
1562:
1558:
1554:
1534:
1531:
1528:
1525:
1522:
1519:
1516:
1513:
1510:
1500:
1496:
1489:
1485:
1464:
1444:
1441:
1438:
1435:
1427:
1424:
1421:
1418:
1412:
1408:
1395:
1393:
1373:
1369:
1365:
1359:
1356:
1353:
1350:
1347:
1344:
1338:
1326:
1308:
1304:
1301:
1295:
1291:
1288:
1282:
1278:
1273:
1269:
1265:
1259:
1254:
1251:
1247:
1244:
1239:
1235:
1230:
1226:
1218:
1217:
1216:
1210:
1192:
1188:
1185:
1179:
1175:
1172:
1166:
1163:
1159:
1154:
1150:
1146:
1140:
1135:
1132:
1129:
1125:
1119:
1116:
1111:
1107:
1103:
1099:
1091:
1090:
1089:
1083:
1081:
1074:
1072:
1066:
1064:
1062:
1058:
1054:
1050:
1045:
1043:
1039:
1020:
1012:
1009:
1006:
1003:
1000:
992:
988:
985:
979:
975:
969:
965:
961:
957:
953:
949:
941:
940:
939:
937:
933:
929:
925:
921:
912:
905:
889:
885:
879:
871:
868:
862:
859:
856:
853:
850:
837:
834:
831:
824:
823:
822:
798:
793:
783:
776:
773:
768:
758:
751:
748:
743:
733:
726:
722:
719:
716:
713:
706:
705:
704:
690:
687:
684:
675:
673:
669:
660:
653:
651:
635:
625:
620:
616:
592:
588:
583:
579:
576:
573:
567:
563:
560:
557:
554:
550:
545:
541:
538:
535:
529:
525:
522:
519:
514:
509:
505:
502:
496:
492:
488:
481:
477:
471:
468:
465:
461:
451:
450:
449:
447:
439:
437:
431:
429:
413:
398:
388:
385:
362:
357:
354:
349:
345:
342:
336:
333:
329:
323:
319:
313:
310:
307:
302:
299:
296:
292:
286:
283:
278:
273:
265:
262:
254:
251:
246:
241:
237:
229:
228:
227:
224:
220:
201:
196:
193:
188:
184:
181:
175:
171:
165:
161:
155:
152:
149:
144:
141:
138:
134:
130:
125:
117:
112:
108:
101:
96:
92:
84:
83:
82:
79:
75:
71:
67:
62:
58:
50:
48:
46:
41:
39:
35:
31:
27:
23:
19:
2392:
2382:
2363:
2357:
2340:
2336:
2330:
2311:
2305:
2259:
2252:
2233:
2223:
2178:
2130:
2124:
2084:(1): 57–82.
2081:
2077:
2071:
2046:
2042:
2036:
1991:
1985:
1952:
1942:
1903:
1897:
1879:1721.1/73474
1862:
1856:
1831:
1827:
1821:
1812:
1808:
1802:
1759:
1755:
1723:
1720:
1704:
1701:
1654:
1646:
1399:
1330:
1214:
1087:
1078:
1070:
1061:filter banks
1052:
1048:
1046:
1041:
1037:
1035:
935:
931:
927:
923:
919:
917:
820:
676:
667:
665:
608:Notice that
607:
445:
443:
435:
377:
222:
218:
216:
77:
73:
60:
56:
54:
42:
21:
17:
15:
2314:. FOCS'19.
1953:Wavelets XI
217:Similarly,
2417:Categories
2402:1609.01361
2373:1609.00896
2321:1909.11123
2270:1604.00845
1925:1581134959
1731:References
444:The phase
51:Definition
2243:1403.5804
2188:1201.2501
2108:1063-5203
2091:1010.0014
2001:1303.1209
1809:SIAM News
1621:
1612:
1577:
1532:
1526:
1517:
1442:
1425:
1360:
1351:
1292:π
1240:∑
1236:−
1211:Repeating
1193:ℓ
1176:π
1164:−
1126:∑
1004:⋅
989:π
860:⋅
854:⋅
723:≡
626:∈
577:π
564:
539:π
526:
506:π
404:→
346:π
334:−
311:−
293:∑
185:π
153:−
135:∑
113:∗
2428:Big data
2297:11847086
2116:16808450
1977:12622592
1934:14320243
1794:14585685
1305:′
1274:′
1248:′
1189:′
1155:′
1108:′
958:′
30:big data
2215:3760962
2063:1631513
2028:6151728
1957:Bibcode
1848:1631513
1764:Bibcode
890:040,300
872:104,134
838:104,134
720:104,134
691:104,134
674:(CRT).
2295:
2285:
2213:
2203:
2157:601496
2155:
2145:
2114:
2106:
2061:
2026:
2016:
1975:
1932:
1922:
1885:
1846:
1792:
1726:. MIT.
1711:
1687:GitHub
1036:where
2397:arXiv
2368:arXiv
2316:arXiv
2293:S2CID
2265:arXiv
2238:arXiv
2211:S2CID
2183:arXiv
2153:S2CID
2112:S2CID
2086:arXiv
2059:S2CID
2024:S2CID
1996:arXiv
1973:S2CID
1930:S2CID
1844:S2CID
1790:S2CID
1752:(PDF)
677:Take
68:. By
2283:ISBN
2201:ISBN
2143:ISBN
2104:ISSN
2014:ISBN
1920:ISBN
1883:ISBN
1815:(4).
1709:ISBN
1051:and
930:and
43:The
16:The
2345:doi
2275:doi
2193:doi
2135:doi
2096:doi
2051:doi
2006:doi
1965:doi
1912:doi
1875:hdl
1867:doi
1836:doi
1780:hdl
1772:doi
1665:ETH
1661:MSU
1657:MIT
1618:log
1609:log
1559:log
1529:log
1523:log
1514:log
1439:log
1422:log
1357:log
1348:log
876:mod
863:103
857:101
851:100
842:mod
799:03.
790:mod
765:mod
740:mod
561:sin
523:cos
64:of
40:.:
34:GPS
22:SFT
2419::
2391:.
2341:41
2339:.
2291:.
2281:.
2273:.
2232:.
2209:.
2199:.
2191:.
2177:.
2165:^
2151:.
2141:.
2110:.
2102:.
2094:.
2082:34
2080:.
2057:.
2047:10
2045:.
2022:.
2012:.
2004:.
1971:.
1963:.
1928:.
1918:.
1881:.
1873:.
1842:.
1832:10
1830:.
1813:33
1811:.
1788:.
1778:.
1770:.
1760:31
1758:.
1754:.
1739:^
1663:,
1659:,
774:01
749:00
734:34
650:.
428:.
72:,
2405:.
2399::
2376:.
2370::
2351:.
2347::
2324:.
2318::
2299:.
2277::
2267::
2246:.
2240::
2217:.
2195::
2185::
2159:.
2137::
2118:.
2098::
2088::
2065:.
2053::
2030:.
2008::
1998::
1979:.
1967::
1959::
1936:.
1914::
1891:.
1877::
1869::
1850:.
1838::
1796:.
1782::
1774::
1766::
1717:.
1627:)
1624:k
1615:n
1606:k
1603:(
1600:O
1580:n
1572:)
1569:d
1566:(
1563:O
1555:k
1535:n
1520:n
1511:k
1506:)
1501:2
1497:d
1493:(
1490:O
1486:2
1465:n
1445:n
1436:k
1431:)
1428:d
1419:d
1416:(
1413:O
1409:2
1380:)
1377:)
1374:k
1370:/
1366:n
1363:(
1354:n
1345:k
1342:(
1339:O
1309:n
1302:k
1296:N
1289:2
1283:j
1279:e
1270:k
1266:X
1260:k
1255:1
1252:=
1245:k
1231:n
1227:x
1186:n
1180:N
1173:2
1167:j
1160:e
1151:n
1147:x
1141:L
1136:1
1133:=
1130:l
1120:L
1117:1
1112:=
1104:k
1100:X
1053:b
1049:c
1042:b
1038:c
1021:,
1016:)
1013:b
1010:+
1007:k
1001:c
998:(
993:N
986:2
980:j
976:e
970:k
966:X
962:=
954:n
950:x
932:b
928:c
924:b
920:c
886:,
880:1
869:=
866:)
846:(
835:=
832:k
794:1
784:1
777:,
769:1
759:3
752:,
744:1
727:{
717:=
714:k
688:=
685:k
668:k
636:N
631:C
621:n
617:x
593:.
589:)
584:N
580:k
574:2
568:(
558:j
555:+
551:)
546:N
542:k
536:2
530:(
520:=
515:k
510:N
503:2
497:j
493:e
489:=
482:n
478:x
472:1
469:+
466:n
462:x
446:k
414:N
409:C
399:N
394:C
389::
386:F
363:.
358:n
355:k
350:N
343:2
337:j
330:e
324:n
320:x
314:1
308:N
303:0
300:=
297:n
287:N
284:1
279:=
274:k
270:)
266:x
263:F
260:(
255:N
252:1
247:=
242:k
238:X
223:k
219:X
202:.
197:n
194:k
189:N
182:2
176:j
172:e
166:k
162:X
156:1
150:N
145:0
142:=
139:k
131:=
126:n
122:)
118:X
109:F
105:(
102:=
97:n
93:x
78:n
74:x
61:n
57:x
20:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
