{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:29Z","timestamp":1750220669760,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,11,30]]},"abstract":"<jats:p>We consider the question of identifying which set of products are purchased and at what prices in a given transaction by observing only the total amount spent in the transaction, and nothing more. The ability to solve such an inverse problem can lead to refined information about consumer spending by simply observing anonymized credit card transactions data. Indeed, when considered in isolation, it is impossible to identify the products purchased and their prices from a given transaction just based on the transaction total. However, given a large number of transactions, there may be a hope. As the main contribution of this work, we provide a robust estimation algorithm for decomposing transaction totals into the underlying, individual product(s) purchased by utilizing a large corpus of transactions. Our method recovers a (product prices) vector $p \\in \\mathbbR ^N_&gt;0 $ of unknown dimension (number of products) N as well as matrix $A \\in \\mathbbZ ^M \\times N _\\geq0 $ simply from M observations (transaction totals) $y \\in \\mathbbR ^M_&gt;0 $ such that $y = A p + \u03b7$ with \u03b7 \\in \\mathbbR ^M$ representing noise (taxes, discounts, etc.). We formally establish that our algorithm identifies $N, A$ precisely and p approximately, as long as each product is purchased individually at least once, i.e. $M \\geq N$ and A has rank N. Computationally, the algorithm runs in polynomial time (with respect to problem parameters), and thus we provide a computationally efficient and statistically robust method for solving such inverse problems. We apply the algorithm to a large corpus of anonymized consumer credit card transactions in the period 2016-2019, with data obtained from a commercial data vendor. The transactions are associated with spending at Apple, Chipotle, Netflix, and Spotify. From just transactions data, our algorithm identifies (i) key price points (without access to the listed prices), (ii) products purchased within a transaction, (iii) product launches, and (iv) evidence of a new 'secret' product from Netflix - rumored to be in limited release.<\/jats:p>","DOI":"10.1145\/3428332","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T19:54:15Z","timestamp":1606766055000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["I Know What You Bought At Chipotle for $9.81 by Solving A Linear Inverse Problem"],"prefix":"10.1145","volume":"4","author":[{"given":"Michael","family":"Fleder","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devavrat","family":"Shah","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"AlternativeData.org. Alternativedata.org database point of sale data. https:\/\/alternativedata.org\/data-providers\/category point-of-sale. Accessed: 2019-05--19."},{"key":"e_1_2_1_2_1","volume-title":"August","author":"Bergen Mark","year":"2018","unstructured":"Mark Bergen and Jennifer Surane. Google and mastercard cut a secret ad deal to track retail sales. https:\/\/www.bloomberg.com\/news\/articles\/2018-08--30\/google-and-mastercard-cut-a-secret-ad-deal-to-track-retail-sales, August 2018. Accessed: 2019-05--19."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2008.4797639"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.3386\/w21305"},{"key":"e_1_2_1_5_1","volume-title":"Near optimal signal recovery from random projections: Universal encoding strategies. arXiv preprint math\/0410542","author":"Candes Emmanuel","year":"2004","unstructured":"Emmanuel Candes and Terence Tao. Near optimal signal recovery from random projections: Universal encoding strategies. arXiv preprint math\/0410542, 2004."},{"key":"e_1_2_1_6_1","volume-title":"The restricted isometry property and its implications for compressed sensing. Comptes rendus mathematique, 346(9--10):589--592","author":"Candes Emmanuel J","year":"2008","unstructured":"Emmanuel J Candes. The restricted isometry property and its implications for compressed sensing. Comptes rendus mathematique, 346(9--10):589--592, 2008."},{"volume-title":"Chipotle online ordering. https:\/\/order.chipotle.com\/Meal\/Index\/1597'showloc=1","year":"2019","key":"e_1_2_1_7_1","unstructured":"Chipotle. Chipotle online ordering. https:\/\/order.chipotle.com\/Meal\/Index\/1597'showloc=1, 2019. Accessed: 2019-05-01."},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009."},{"key":"e_1_2_1_9_1","volume-title":"November","author":"Dezember Ryan","year":"2018","unstructured":"Ryan Dezember. Your smartphone's location data is worth big money to wall street. https:\/\/www.wsj.com\/articles\/your-smartphones-location-data-is-worth-big-money-to-wall-street-1541131260, November 2018. Accessed: 2018--11-04."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_2_1_11_1","unstructured":"DVD.COM. Dvd.com choose a plan. https:\/\/dvd.netflix.com\/Plans?dsrc=DVDWEB_NMHOME_NMHEADER_PLANS. Accessed: 2019-05--27."},{"key":"e_1_2_1_12_1","volume-title":"September","author":"Efrati Amir","year":"2018","unstructured":"Amir Efrati. U.S. slowdown at Uber and Lyft. https:\/\/www.theinformation.com\/articles\/u-s-slowdown-at-uber-and-lyft, September 2018. Accessed: 2018--10--25."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3393691.3394187"},{"key":"e_1_2_1_14_1","volume-title":"April","author":"Hope Bradley","year":"2015","unstructured":"Bradley Hope. Provider of personal finance tools tracks bank cards sells data to investors. https:\/\/www.wsj.com\/articles\/provider-of-personal-finance-tools-tracks-bank-cards-sells-data-to-investors-1438914620, April 2015. Accessed: 2018-05--10."},{"key":"e_1_2_1_15_1","volume-title":"April","author":"C.","year":"2019","unstructured":"IO&C. The big trends in data reshaping financial industry. https:\/\/ioandc.com\/the-big-trends-in-data-reshaping-financial-industry, April 2019. Accessed: 2019-04-07."},{"key":"e_1_2_1_16_1","volume-title":"Pearson Education India","author":"Kleinberg Jon","year":"2006","unstructured":"Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education India, 2006."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-4101(01)00030-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345697"},{"key":"e_1_2_1_19_1","unstructured":"Netflix. Netflix pick your price. https:\/\/www.netflix.com. Accessed: 2019-05--27."},{"key":"e_1_2_1_20_1","volume-title":"April","author":"Perez Sarah","year":"2018","unstructured":"Sarah Perez. Spotify and Hulu launch a discounted entertainment bundle for $$12.99$. https:\/\/techcrunch.com\/2018\/04\/11\/spotify-and-hulu-launch-a-discounted-entertainment-bundle-for-12--99-per-month, April 2018. Accessed: 2019-06--11."},{"key":"e_1_2_1_21_1","unstructured":"Ashley Rodriguez. A history of netflix us price hikes charted. https:\/\/qz.com\/1524449\/netflix-just-raised-prices-in-the-us-a-history-of-hikes-charted. Accessed: 2019-05--27."},{"key":"e_1_2_1_22_1","unstructured":"Second Measure. Data points. https:\/\/secondmeasure.com\/datapoints. Accessed: 2019-05--19."},{"key":"e_1_2_1_23_1","volume-title":"July","author":"Spangler Todd","year":"2018","unstructured":"Todd Spangler. Netflix testing out pricier new \"Ultra\" plan at $16.99 per month. https:\/\/variety.com\/2018\/digital\/news\/netflix-ultra-plan-hdr-ultrahd-test-1202865305, July 2018. Accessed: 2019-05--27."},{"key":"e_1_2_1_24_1","volume-title":"January","author":"Wigglesworth Robin","year":"2018","unstructured":"Robin Wigglesworth. Asset management's fight for alternative data analysts heats up. https:\/\/www.ft.com\/content\/2f454550-02c8--11e8--9650--9c0ad2d7c5b5, January 2018. Accessed: 2018-05-07."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:58Z","timestamp":1750197778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3428332"],"URL":"https:\/\/doi.org\/10.1145\/3428332","relation":{},"ISSN":["2476-1249"],"issn-type":[{"type":"electronic","value":"2476-1249"}],"subject":[],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"2020-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}