Piotr Indyk
- Nir Ailon and Bernard Chazelle. Faster dimension reduction. Communications of the ACM, 53(2):97--104, 2010. Google Scholar
Digital Library
- A. Akavia, S. Goldwasser, and S. Safra. Proving hard-core predicates using list decoding. FOCS, 44:146--159, 2003. Google ScholarDigital Library
- A. Akavia. Deterministic sparse Fourier approximation via fooling arithmetic progressions. COLT, pages 381--393, 2010.Google Scholar
- Nir Ailon and Edo Liberty. An almost optimal unrestricted fast Johnson-Lindenstrauss transform. SODA, pages 185--191, 2011. Google ScholarDigital Library
- 2}BCGLSP. Boufounos, V. Cevher, A. C. Gilbert, Y. Li, and M. J. Strauss. What's the frequency, kenneth?: Sublinear Fourier sampling off the grid. RANDOM/APPROX, 2012.Google ScholarCross Ref
- R. Berinde, A. Gilbert, P. Indyk, H. Karloff, and M. Strauss. Combining geometry and combinatorics: a unified approach to sparse signal recovery. Allerton, 2008.Google ScholarCross Ref
- R. Berinde, P. Indyk, and M. Ruzic. Practical near-optimal sparse recovery in the l_1 norm. Allerton, 2008.Google ScholarCross Ref
- Mayank Bakshi, Sidharth Jaggi, Sheng Cai, and Minghua Chen. Sho-fa: Robust compressive sensing with order-optimal complexity, measurements, and bits. arXiv preprint arXiv:1207.2335, 2012.Google Scholar
- Andrei Broder and Michael Mitzenmacher. Network applications of bloom filters: A survey. Internet Mathematics, 1(4):485--509, 2004.Google ScholarCross Ref
- Vladimir Braverman, Rafail Ostrovsky, and Yuval Rabani. Rademacher chaos, random eulerian graphs and the sparse Johnson-Lindenstrauss transform. arXiv preprint arXiv:1011.2590, 2010.Google Scholar
- M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. ICALP, 2002. Google ScholarDigital Library
- Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker. Restricted isometry of Fourier matrices and list decodability of random linear codes. SODA, 2013.Google ScholarCross Ref
- Saar Cohen and Yossi Matias. Spectral bloom filters. SIGMOD, pages 241--252, 2003. Google ScholarDigital Library
- Graham Cormode and S. Muthukrishnan. What's hot and what's not: tracking most frequent items dynamically. PODS, pages 296--306, 2003. Google ScholarDigital Library
- G. Cormode and S. Muthukrishnan. Improved data stream summaries: The count-min sketch and its applications. LATIN, 2004.Google ScholarCross Ref
- G. Cormode and S. Muthukrishnan. Combinatorial algorithms for Compressed Sensing. Proc. 40th Ann. Conf. Information Sciences and Systems, Mar. 2006. Google ScholarDigital Library
- E. J. Candès, J. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59(8):1208--1223, 2006.Google ScholarCross Ref
- Emmanuel J Candes and Terence Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? Information Theory, IEEE Transactions on, 52(12):5406--5425, 2006. Google ScholarDigital Library
- Kenneth L Clarkson and David P Woodruff. Low rank approximation and regression in input sparsity time. STOC, 2013. Google ScholarDigital Library
- K. Do Ba, P. Indyk, E. Price, and D. Woodruff. Lower bounds for sparse recovery. SODA, 2010. Google ScholarDigital Library
- Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse Johnson-Lindenstrauss transform. STOC, pages 341--350, 2010. Google ScholarDigital Library
- D. L. Donoho. Compressed Sensing. Information Theory, IEEE Transactions on, 52(4):1289--1306, Apr. 2006. Google ScholarDigital Library
- Cristian Estan and George Varghese. New directions in traffic measurement and accounting. SIGCOMM, 2002. Google ScholarDigital Library
- Li Fan, Pei Cao, Jussara M. Almeida, and Andrei Z. Broder. Summary cache: A scalable wide-area web cache sharing protocol. SIGCOMM, pages 254--265, 1998. Google ScholarDigital Library
- S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich. The gelfand widths of lp-balls for 0 < p łeq 1. preprint, 2010.Google Scholar
- Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D Ullman. Computing iceberg queries efficiently. VLDB, 1998. Google ScholarDigital Library
- A. Gilbert, S. Guha, P. Indyk, M. Muthukrishnan, and M. Strauss. Near-optimal sparse Fourier representations via sampling. STOC, 2002. Google ScholarDigital Library
- A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. Fast, small-space algorithms for approximate histogram maintenance. STOC, 2002. Google ScholarDigital Library
- Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi. Sample-optimal average-case sparse fourier transform in two dimensions. arXiv preprint arXiv:1303.1209, 2013.Google Scholar
- A. Gilbert and P. Indyk. Sparse recovery using sparse matrices. Proceedings of IEEE, 2010.Google ScholarCross Ref
- Anna Gilbert, Piotr Indyk, Dina Katabi, and Ramesh Raskar. Workshop on sparse Fourier transform etc. http://groups.csail.mit.edu/ netmit/sFFT/workshop.html, 2013.Google Scholar
- O. Goldreich and L. Levin. A hard-corepredicate for all one-way functions. STOC, pages 25--32, 1989. Google ScholarDigital Library
- A. C. Gilbert, Y. Li, E. Porat, and M. J. Strauss. Approximate sparse recovery: optimizing time and measurements. STOC, pages 475--484, 2010. Google ScholarDigital Library
- Michael T Goodrich and Michael Mitzenmacher. Invertible bloom lookup tables. In Allerton, pages 792--799, 2011.Google ScholarCross Ref
- A. Gilbert, M. Muthukrishnan, and M. Strauss. Improved time bounds for near-optimal space Fourier representations. SPIE Conference, Wavelets, 2005.Google Scholar
- O. Goldreich. Modern cryptography, probabilistic proofs and pseudorandomness. Algorithms and Combinatorics, 17, 1999.Google Scholar
- Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer. Testing fourier dimensionality and sparsity. SIAM J. Comput., 40(4):1075--1100, 2011. Google ScholarDigital Library
- A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin. One sketch for all: fast algorithms for compressed sensing. STOC, pages 237--246, 2007. Google ScholarDigital Library
- H. Hassanieh, P. Indyk, D. Katabi, and E. Price. Near-optimal algorithm for sparse Fourier transform. STOC, 2012. Google ScholarDigital Library
- H. Hassanieh, P. Indyk, D. Katabi, and E. Price. Simple and practical algorithm for sparse Fourier transform. SODA, 2012. Google ScholarDigital Library
- Sabine Heider, Stefan Kunis, Daniel Potts, and Michael Veit. A sparse prony fft. 2013.Google Scholar
- P. Indyk. Explicit constructions for compressed sensing of sparse signals. SODA, 2008. Google ScholarDigital Library
- P. Indyk and M. Ruzic. Near-optimal sparse recovery in the $l_1$ norm. FOCS, 2008. Google ScholarDigital Library
- M. A. Iwen. Combinatorial sublinear-time Fourier algorithms. Foundations of Computational Mathematics, 10:303--338, 2010. Google ScholarDigital Library
- M.A. Iwen. Improved approximation guarantees for sublinear-time Fourier algorithms. Applied And Computational Harmonic Analysis, 2012.Google Scholar
- W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mapping into Hilbert space. Conf. in modern analysis and probability, 26:189--206, 1984.Google ScholarCross Ref
- S. Jafarpour, W. Xu, B. Hassibi, and A. R. Calderbank. Efficient and robust compressed sensing using high-quality expander graphs. Information Theory, IEEE Transactions on, 55(9):4299--4308, 2009. Google ScholarDigital Library
- M. A. Khajehnejad, A. G. Dimakis, W. Xu, and B. Hassibi. Sparse recovery of positive signals with minimal expansion. Signal Processing, IEEE Transactions on, 59(1):196--208, 2011. Google ScholarDigital Library
- E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. STOC, 1991. Google ScholarDigital Library
- Daniel M Kane and Jelani Nelson. Sparser Johnson-Lindenstrauss transforms. SODA, pages 1195--1206, 2012. Google ScholarDigital Library
- Felix Krahmer and Rachel Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 43(3):1269--1281, 2011.Google ScholarCross Ref
- L.A. Levin. Randomness and non-determinism. J. Symb. Logic, 58(3):1102--1103, 1993.Google Scholar
- Y. Lu, A. Montanari, B. Prabhakar, S. Dharmapurikar, and A. Kabbani. Counter braids: A novel counter architecture for per-flow measurement. SIGMETRICS, 2008. Google ScholarDigital Library
- D. Lawlor, Y. Wang, and A. Christlieb. Adaptive sub-linear time Fourier algorithms. arXiv:1207.6368, 2012.Google Scholar
- Y. Mansour. Randomized interpolation and approximation of sparse polynomials. ICALP, 1992. Google ScholarDigital Library
- Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. STOC, 2013. Google ScholarDigital Library
- S Muthukrishnan. Data streams: Algorithms and applications. Now Publishers Inc, 2005.Google ScholarCross Ref
- Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. arXiv preprint arXiv:1211.1002, 2012.Google Scholar
- Jelani Nelson, Eric Price, and Mary Wootters. New constructions of RIP matrices with fast multiplication and fewer rows. CoRR, abs/1211.0986, 2012.Google Scholar
- Sameer Pawar and Kannan Ramchandran. A hybrid dft-ldpc framework for fast, efficient and robust compressive sensing. In Allerton, pages 1943--1950, 2012.Google ScholarCross Ref
- M. Rudelson and R. Veshynin. Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements. Proc. 40th Ann. Conf. Information Sciences and Systems, Mar. 2006.Google ScholarCross Ref
- S. Sarvotham, D. Baron, and R. G. Baraniuk. Sudocodes - fast measurement and reconstruction of sparse signals. IEEE International Symposium on Information Theory, 2006.Google Scholar
- S. Sarvotham, D. Baron, and R. G. Baraniuk. Bayesian compressive sensing via belief propagation. Signal Processing, IEEE Transactions on, 58(1):269--280, 2010. Google ScholarDigital Library
- Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vishwanathan. Hash kernels for structured data. The Journal of Machine Learning Research, 10:2615--2637, 2009. Google ScholarDigital Library
- Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. ICML, pages 1113--1120, 2009. Google ScholarDigital Library
- Wei Wang, Minos Garofalakis, and Kannan Ramchandran. Distributed sparse random projections for refinable approximation. IPSN, pages 331--339, 2007. Google ScholarDigital Library
- W. Wang, M. J. Wainwright, and K. Ramchandran. Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices. Information Theory, IEEE Transactions on, 56(6):2967--2979, 2010. Google ScholarDigital Library
- W. Xu and B. Hassibi. Efficient compressive sensing with determinstic guarantees using expander graphs. IEEE InformationGoogle Scholar
Index Terms
- Sketching via hashing: from heavy hitters to compressed sensing to sparse fourier transform
Recommendations
Image compressive sensing recovery using adaptively learned sparsifying basis via L0 minimization
From many fewer acquired measurements than suggested by the Nyquist sampling theory, compressive sensing (CS) theory demonstrates that, a signal can be reconstructed with high probability when it exhibits sparsity in some domain. Most of the ...
Image compressed sensing recovery via nonconvex garrote regularization
AbstractSparsity inducing model is one of the most important components of image compressed sensing (CS) recovery methods. These models are built on the image prior knowledge. The model which can reflect the image priors appropriately, yields high quality ...
Two‐dimensional sparse fractional Fourier transform and its applications
Highlights- Efficient estimation of sampled 2D DFRFT utilizing the sparse nature of the signal.
AbstractThe discrete fractional Fourier transform is an excellent tool in non-stationary signal processing. And an efficient and accurate computation is important for the two-dimensional discrete fractional Fourier transform (2D DFRFT). ...
Comments