{"id":188880,"date":"2013-01-14T00:00:00","date_gmt":"2013-01-15T12:21:58","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/fourier-sampling-and-beyond\/"},"modified":"2016-08-10T07:17:30","modified_gmt":"2016-08-10T14:17:30","slug":"fourier-sampling-and-beyond","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/fourier-sampling-and-beyond\/","title":{"rendered":"Fourier Sampling and Beyond"},"content":{"rendered":"<div class=\"asset-content\">\n<p>The Fast Fourier Transform (FFT) is a fundamental algorithm that computes the Discrete Fourier Transform of an n-dimensional signal in O(n log n) time.  It is unknown whether the running time can be improved in general.  However, in applications such as image, audio, and video compression where the output is &#8220;sparse&#8221; (i.e., k  n coordinates are &#8220;large&#8221; and contain most of the energy), it is possible to estimate the large coordinates in less than O(n log n) time.  We show the first algorithms that achieve this for any k = o(n).<\/p>\n<p>The sparse Fourier transform problem lies in the broader area of sparse recovery or compressive sensing.  This area considers the robust recovery of a sparse vector x from relatively few linear measurements Ax, and has applications in diverse settings such as streaming algorithms, camera design, and genetic testing.  We discuss multiple extensions to the sparse recovery framework, including a proof that the number of measurement can be improved \u2013 in some cases exponentially \u2013 if the measurements are chosen <i>adaptively<\/i>.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Fast Fourier Transform (FFT) is a fundamental algorithm that computes the Discrete Fourier Transform of an n-dimensional signal in O(n log n) time. It is unknown whether the running time can be improved in general. However, in applications such as image, audio, and video compression where the output is &#8220;sparse&#8221; (i.e., k n coordinates [&hellip;]<\/p>\n","protected":false},"featured_media":197381,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-188880","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/5vH8snamEI8","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/188880"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/188880\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/197381"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=188880"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=188880"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=188880"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=188880"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=188880"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=188880"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}