Paper Search Console

Home Search Page About Contact

Journal Title

Title of Journal: Algorithmica

Search In Journal Title:

Abbravation: Algorithmica

Search In Journal Abbravation:

Publisher

Springer US

Search In Publisher:

DOI

10.1007/bf02510936

Search In DOI:

ISSN

1432-0541

Search In ISSN:
Search In Title Of Papers:

What’s the Frequency Kenneth Sublinear Fourier

Authors: Petros Boufounos Volkan Cevher Anna C Gilbert Yi Li Martin J Strauss
Publish Date: 2014/07/22
Volume: 73, Issue: 2, Pages: 261-288
PDF Link

Abstract

We design a sublinear Fourier sampling algorithm for a case of sparse offgrid frequency recovery These are signals with the form ft = sum j=1k a j mathrmeiomega j t + int nu omega mathrmeiomega tdmu omega ie exponential polynomials with a noise term The frequencies omega j satisfy omega jin eta 2pi eta and min ine j omega iomega jge eta for some eta 0 We design a sublinear time randomized algorithm which for any epsilon in 0eta /k which takes Oklog klog 1/epsilon log k+log Vert aVert 1/Vert nu Vert 1 samples of ft and runs in time proportional to number of samples recovering omega japprox omega j and a japprox a j such that with probability varOmega 1 the approximation error satisfies omega jomega jle epsilon and a ja jle Vert nu Vert 1/k for all j with a jge Vert nu Vert 1/k We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processingThe authors would like to thank an anonymous reviewer of APPROX/RANDOM 2012 for the suggestion of improving the running time V Cevher was partially supported by Faculty Fellowship at Rice University MIRG268398 ERC Future Proof and DARPA KeCoM program 11DARPA1055 A C Gilbert was partially supported by NSF DMS 0743372 and DARPA ONR N660010612011 Y Li was partially supported by NSF DMS 0743372 when the author was at University of Michigan Ann Arbor M J Strauss was partially supported by NSF DMS 0743372 and DARPA ONR N660010612011


Keywords:

References


.
Search In Abstract Of Papers:
Other Papers In This Journal:

  1. On Minimum Sum of Radii and Diameters Clustering
  2. Integer Representation and Counting in the Bit Probe Model
  3. An Efficient Fixed Parameter Tractable Algorithm for 1-Sided Crossing Minimization
  4. New Approximation Algorithms for Minimum Cycle Bases of Graphs
  5. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
  6. Aligning Two Convex Figures to Minimize Area or Perimeter
  7. Introduction for S.I. AofA14
  8. Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness
  9. Detecting Regular Visit Patterns
  10. Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
  11. Random Matrices and Codes for the Erasure Channel
  12. On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs
  13. The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
  14. Optimal Parallel Quantum Query Algorithms
  15. Average Case Network Lifetime on an Interval with Adjustable Sensing Ranges
  16. Maximum Series-Parallel Subgraph
  17. A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
  18. Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets
  19. The Parameterized Complexity of Local Search for TSP, More Refined
  20. Approximating Fixation Probabilities in the Generalized Moran Process
  21. Approximation Algorithms for Scheduling with Reservations
  22. Algorithms for the Homogeneous Set Sandwich Problem
  23. A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
  24. Computing Minimum Cuts by Randomized Search Heuristics
  25. Constructing Labeling Schemes through Universal Matrices
  26. An Approximation Algorithm for the Minimum Co-Path Set Problem
  27. Scheduling with an Orthogonal Resource Constraint
  28. Approximate Boyer-Moore String Matching for Small Alphabets
  29. Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
  30. Between Treewidth and Clique-Width
  31. Multi-sided Boundary Labeling
  32. A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs

Search Result: