{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:58:57Z","timestamp":1725469137463},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_53","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"627-638","source":"Crossref","is-referenced-by-count":4,"title":["On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation"],"prefix":"10.1007","author":[{"given":"Jelani","family":"Nelson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huy L.","family":"Nguy\u00ea\u0303n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"53_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D. Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci.\u00a066(4), 671\u2013687 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"53_CR2","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"N. Ailon","year":"2009","unstructured":"Ailon, N., Chazelle, B.: The fast Johnson-Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput.\u00a039(1), 302\u2013322 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"53_CR3","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1007\/s00454-008-9110-x","volume":"42","author":"N. Ailon","year":"2009","unstructured":"Ailon, N., Liberty, E.: Fast dimension reduction using Rademacher series on dual BCH codes. Discrete & Computational Geometry\u00a042(4), 615\u2013630 (2009)","journal-title":"Discrete & Computational Geometry"},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"Ailon, N., Liberty, E.: Almost optimal unrestricted fast Johnson-Lindenstrauss transform. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 185\u2013191 (2011)","DOI":"10.1137\/1.9781611973082.17"},{"issue":"1-3","key":"53_CR5","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0012-365X(03)00227-9","volume":"273","author":"N. Alon","year":"2003","unstructured":"Alon, N.: Problems and results in extremal combinatorics - I. Discrete Mathematics\u00a0273(1-3), 31\u201353 (2003)","journal-title":"Discrete Mathematics"},{"issue":"1-2","key":"53_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1017\/S0963548307008917","volume":"18","author":"N. Alon","year":"2009","unstructured":"Alon, N.: Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability & Computing\u00a018(1-2), 3\u201315 (2009)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"3","key":"53_CR7","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Rand. Struct. Alg.\u00a03(3), 289\u2013304 (1992)","journal-title":"Rand. Struct. Alg."},{"issue":"1","key":"53_CR8","first-page":"137","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The Space Complexity of Approximating the Frequency Moments. JCSS\u00a058(1), 137\u2013147 (1999)","journal-title":"JCSS"},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"Ba, K.D., Indyk, P., Price, E., Woodruff, D.P.: Lower bounds for sparse recovery. In: SODA, pp. 1190\u20131197 (2010)","DOI":"10.1137\/1.9781611973075.95"},{"issue":"3","key":"53_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00365-007-9003-x","volume":"28","author":"R. Baraniuk","year":"2008","unstructured":"Baraniuk, R., Davenport, M.A., DeVore, R., Wakin, M.: A simple proof of the Restricted Isometry Property. Constructive Approximation\u00a028(3), 253\u2013263 (2008)","journal-title":"Constructive Approximation"},{"key":"53_CR11","doi-asserted-by":"crossref","unstructured":"Barbar\u00e1, D., Wu, N., Jajodia, S.: Detecting novel network intrusions using Bayes estimators. In: Proceedings of the 1st SIAM International Conference on Data Mining (2001)","DOI":"10.1137\/1.9781611972719.28"},{"issue":"2","key":"53_CR12","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E. Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Information Theory\u00a052(2), 489\u2013509 (2006)","journal-title":"IEEE Trans. Information Theory"},{"issue":"1","key":"53_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M. Charikar","year":"2004","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theor. Comput. Sci.\u00a0312(1), 3\u201315 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1090\/S0894-0347-08-00610-3","volume":"22","author":"A. Cohen","year":"2009","unstructured":"Cohen, A., Dahmen, W., DeVore, R.A.: Compressed sensing and best k-term approximation. J. Amer. Math. Soc.\u00a022, 211\u2013231 (2009)","journal-title":"J. Amer. Math. Soc."},{"issue":"1","key":"53_CR15","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms\u00a055(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"53_CR16","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1145\/1061318.1061325","volume":"30","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: What\u2019s hot and what\u2019s not: tracking most frequent items dynamically. ACM Trans. Database Syst.\u00a030(1), 249\u2013278 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"53_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/3-540-45749-6_33","volume-title":"Algorithms - ESA 2002","author":"E.D. Demaine","year":"2002","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Frequency Estimation of Internet Packet Streams with Limited Space. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 348\u2013360. Springer, Heidelberg (2002)"},{"key":"53_CR18","doi-asserted-by":"publisher","first-page":"2558","DOI":"10.1109\/18.959265","volume":"47","author":"D.L. Donoho","year":"2001","unstructured":"Donoho, D.L., Huo, X.: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inform. Th.\u00a047, 2558\u20132567 (2001)","journal-title":"IEEE Trans. Inform. Th."},{"issue":"6","key":"53_CR19","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.jco.2010.04.004","volume":"26","author":"S. Foucart","year":"2010","unstructured":"Foucart, S., Pajor, A., Rauhut, H., Ullrich, T.: The Gelfand widths of \u2113\n                    p\n                  -balls for 0\u2009<\u2009p\u2009\u2264\u20091. Journal of Complexity\u00a026(6), 629\u2013640 (2010)","journal-title":"Journal of Complexity"},{"key":"53_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/978-3-540-79709-8_22","volume-title":"Computer Science \u2013 Theory and Applications","author":"S. Ganguly","year":"2008","unstructured":"Ganguly, S.: Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract). In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol.\u00a05010, pp. 204\u2013215. Springer, Heidelberg (2008)"},{"key":"53_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-02026-1_28","volume-title":"Combinatorial Optimization and Applications","author":"S. Ganguly","year":"2009","unstructured":"Ganguly, S.: Deterministically Estimating Data Stream Frequencies. In: Du, D.-Z., Hu, X., Pardalos, P.M. (eds.) COCOA 2009. LNCS, vol.\u00a05573, pp. 301\u2013312. Springer, Heidelberg (2009)"},{"key":"53_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-74450-4_5","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"S. Ganguly","year":"2007","unstructured":"Ganguly, S., Majumder, A.: CR-precis: A Deterministic Summary Structure for Update Data Streams. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 48\u201359. Springer, Heidelberg (2007)"},{"key":"53_CR23","first-page":"200","volume":"30","author":"A.Y. Garnaev","year":"1984","unstructured":"Garnaev, A.Y., Gluskin, E.D.: On the widths of the Euclidean ball. Soviet Mathematics Doklady\u00a030, 200\u2013203 (1984)","journal-title":"Soviet Mathematics Doklady"},{"key":"53_CR24","unstructured":"Gilbert, A.C., Kotidis, Y., Muthukrishnan, S., Strauss, M.J.: Quicksand: Quick summary and analysis of network data. DIMACS Technical Report 2001-43 (2001)"},{"key":"53_CR25","unstructured":"Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Approximation of functions over redundant dictionaries using coherence. In: SODA, pp. 243\u2013252 (2003)"},{"key":"53_CR26","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Strauss, M.J., Tropp, J.A., Vershynin, R.: One sketch for all: fast algorithms for compressed sensing. In: STOC, pp. 237\u2013246 (2007)","DOI":"10.1145\/1250790.1250824"},{"key":"53_CR27","first-page":"163","volume":"14","author":"E.D. Gluskin","year":"1982","unstructured":"Gluskin, E.D.: On some finite-dimensional problems in the theory of widths. Vestn. Leningr. Univ. Math.\u00a014, 163\u2013170 (1982)","journal-title":"Vestn. Leningr. Univ. Math."},{"key":"53_CR28","doi-asserted-by":"crossref","unstructured":"Indyk, P., Ru\u017ei\u0107, M.: Near-optimal sparse recovery in the L\n                  1 norm. In: FOCS, pp. 199\u2013207 (2008)","DOI":"10.1109\/FOCS.2008.82"},{"key":"53_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"key":"53_CR30","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for L\n                  \n                    p\n                   samplers, finding duplicates in streams, and related problems. In: PODS, pp. 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"53_CR31","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J.: Sparser Johnson-Lindenstrauss transforms. In: SODA, pp. 1195\u20131206 (2012)","DOI":"10.1137\/1.9781611973099.94"},{"key":"53_CR32","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1145\/762471.762473","volume":"28","author":"R.M. Karp","year":"2003","unstructured":"Karp, R.M., Shenker, S., Papadimitriou, C.H.: A simple algorithm for finding frequent elements in streams and bags. ACM Trans. Database Syst.\u00a028, 51\u201355 (2003)","journal-title":"ACM Trans. Database Syst."},{"key":"53_CR33","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TIT.1964.1053689","volume":"10","author":"W.H. Kautz","year":"1964","unstructured":"Kautz, W.H., Singleton, R.C.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theory\u00a010, 363\u2013377 (1964)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"53_CR34","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1137\/100810447","volume":"43","author":"F. Krahmer","year":"2011","unstructured":"Krahmer, F., Ward, R.: New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property. SIAM J. Math. Anal.\u00a043(3), 1269\u20131281 (2011)","journal-title":"SIAM J. Math. Anal."},{"key":"53_CR35","volume-title":"Computational Number Theory and Digital Signal Processing: Fast Algorithms and Error Control Techniques","author":"H. Krishna","year":"1994","unstructured":"Krishna, H., Krishna, B., Lin, K.-Y., Sun, J.-D.: Computational Number Theory and Digital Signal Processing: Fast Algorithms and Error Control Techniques. CRC, Boca Raton (1994)"},{"issue":"12","key":"53_CR36","doi-asserted-by":"publisher","first-page":"3397","DOI":"10.1109\/78.258082","volume":"41","author":"S.G. Mallat","year":"1993","unstructured":"Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process.\u00a041(12), 3397\u20133415 (1993)","journal-title":"IEEE Trans. Signal Process."},{"issue":"2","key":"53_CR37","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0167-6423(82)90012-0","volume":"2","author":"J. Misra","year":"1982","unstructured":"Misra, J., Gries, D.: Finding repeated elements. Sci. Comput. Program.\u00a02(2), 143\u2013152 (1982)","journal-title":"Sci. Comput. Program."},{"issue":"4","key":"53_CR38","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput.\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"53_CR39","doi-asserted-by":"crossref","unstructured":"Price, E., Woodruff, D.P.: (1 + eps)-approximate sparse recovery. In: FOCS, pp. 295\u2013304 (2011)","DOI":"10.1109\/FOCS.2011.92"},{"key":"53_CR40","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1002\/cpa.20227","volume":"61","author":"M. Rudelson","year":"2008","unstructured":"Rudelson, M., Vershynin, R.: On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics\u00a061, 1025\u20131045 (2008)","journal-title":"Communications on Pure and Applied Mathematics"},{"key":"53_CR41","doi-asserted-by":"crossref","unstructured":"Sivakumar, D.: Algorithmic derandomization via complexity theory. In: STOC, pp. 619\u2013626 (2002)","DOI":"10.1145\/509907.509996"},{"key":"53_CR42","volume-title":"Residue Number System Arithmetic: Modern Applications in Digital Signal Processing","author":"M.A. Soderstrand","year":"1986","unstructured":"Soderstrand, M.A., Jenkins, W.K., Jullien, G.A., Taylor, F.J.: Residue Number System Arithmetic: Modern Applications in Digital Signal Processing. IEEE Press, New York (1986)"},{"key":"53_CR43","unstructured":"von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press (1999)"},{"issue":"12","key":"53_CR44","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1109\/PROC.1966.5275","volume":"4","author":"R.W. Watson","year":"1966","unstructured":"Watson, R.W., Hastings, C.W.: Self-checked computation using residue arithmetic. Proc. IEEE\u00a04(12), 1920\u20131931 (1966)","journal-title":"Proc. IEEE"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:05:40Z","timestamp":1620129940000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}