{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:40:54Z","timestamp":1742913654540,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031327254"},{"type":"electronic","value":"9783031327261"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-32726-1_4","type":"book-chapter","created":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:28:43Z","timestamp":1684700923000},"page":"44-57","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparse Approximation over\u00a0the\u00a0Cube"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5673-3383","authenticated-orcid":false,"given":"Sabrina","family":"Bruckmeier","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5580-3677","authenticated-orcid":false,"given":"Christoph","family":"Hunkenschr\u00f6der","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Weismantel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,22]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","unstructured":"Ament, S., Gomes, C.: On the optimality of backward regression: Sparse recovery and subset selection. In: ICASSP 2021\u20132021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), June 2021. https:\/\/doi.org\/10.1109\/icassp39728.2021.9415082","DOI":"10.1109\/icassp39728.2021.9415082"},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Beale, E.M.L., Kendall, M.G., Mann, D.W.: The discarding of variables in multivariate analysis. Biometrika 54(3\u20134), 357\u2013366 (1967). https:\/\/doi.org\/10.1093\/biomet\/54.3-4.357","DOI":"10.1093\/biomet\/54.3-4.357"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E Candes","year":"2006","unstructured":"Candes, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489\u2013509 (2006). https:\/\/doi.org\/10.1109\/TIT.2005.862083","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"4_CR4","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"E Candes","year":"2005","unstructured":"Candes, E., Tao, T.: Decoding by linear programming. IEEE Trans. Inf. Theory 51(12), 4203\u20134215 (2005). https:\/\/doi.org\/10.1109\/TIT.2005.858979","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"4_CR5","doi-asserted-by":"publisher","first-page":"2313","DOI":"10.1214\/009053606000001523","volume":"35","author":"E Candes","year":"2007","unstructured":"Candes, E., Tao, T.: The Dantzig selector: statistical estimation when p is much larger than n. Ann. Stat. 35(6), 2313\u20132351 (2007). https:\/\/doi.org\/10.1214\/009053606000001523","journal-title":"Ann. Stat."},{"issue":"8","key":"4_CR6","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Candes","year":"2006","unstructured":"Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006). https:\/\/doi.org\/10.1002\/cpa.20124","journal-title":"Commun. Pure Appl. Math."},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1137\/S1064827596304010","volume":"43","author":"SS Chen","year":"2001","unstructured":"Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Rev. 43(1), 129\u2013159 (2001). https:\/\/doi.org\/10.1137\/S1064827596304010","journal-title":"SIAM Rev."},{"issue":"3","key":"4_CR8","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/S0895479898332928","volume":"21","author":"C Couvreur","year":"2000","unstructured":"Couvreur, C., Bresler, Y.: On the optimality of the backward greedy algorithm for the subset selection problem. SIAM J. Matrix Anal. Appl. 21(3), 797\u2013808 (2000). https:\/\/doi.org\/10.1137\/S0895479898332928","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"4_CR9","doi-asserted-by":"publisher","unstructured":"Das, A., Kempe, D.: Algorithms for subset selection in linear regression. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC 2008, pp. 45\u201354. Association for Computing Machinery, New York (2008). https:\/\/doi.org\/10.1145\/1374376.1374384","DOI":"10.1145\/1374376.1374384"},{"key":"4_CR10","doi-asserted-by":"publisher","unstructured":"Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of the 28th International Conference on International Conference on Machine Learning. ICML 2011, pp. 1057\u20131064. Omnipress, Madison (2011). https:\/\/doi.org\/10.5555\/3104482.3104615","DOI":"10.5555\/3104482.3104615"},{"issue":"2","key":"4_CR11","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1137\/18M1219266","volume":"30","author":"A Del Pia","year":"2020","unstructured":"Del Pia, A., Dey, S.S., Weismantel, R.: Subset selection in sparse matrices. SIAM J. Optim. 30(2), 1173\u20131190 (2020). https:\/\/doi.org\/10.1137\/18M1219266","journal-title":"SIAM J. Optim."},{"key":"4_CR12","doi-asserted-by":"publisher","unstructured":"Di Lorenzo, D., Liuzzi, G., Rinaldi, F., Schoen, F., Sciandrone, M.: A concave optimization-based approach for sparse portfolio selection. Optim. Methods Softw. 27(6), 983\u20131000 (2012). https:\/\/doi.org\/10.1080\/10556788.2011.577773","DOI":"10.1080\/10556788.2011.577773"},{"issue":"4","key":"4_CR13","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D Donoho","year":"2006","unstructured":"Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289\u20131306 (2006). https:\/\/doi.org\/10.1109\/TIT.2006.871582","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6B","key":"4_CR14","doi-asserted-by":"publisher","first-page":"3539","DOI":"10.1214\/17-AOS1679","volume":"46","author":"ER Elenberg","year":"2018","unstructured":"Elenberg, E.R., Khanna, R., Dimakis, A.G., Negahban, S.: Restricted strong convexity implies weak submodularity. Ann. Stat. 46(6B), 3539\u20133568 (2018). https:\/\/doi.org\/10.1214\/17-AOS1679","journal-title":"Ann. Stat."},{"issue":"2","key":"4_CR15","first-page":"273","volume":"14","author":"M Feng","year":"2018","unstructured":"Feng, M., Mitchell, J.J., Pang, J.S., Shen, X., Waechter, A.: Complementarity formulations of $$\\ell _0$$-norm optimization. Pac. J. Optim. 14(2), 273\u2013305 (2018)","journal-title":"Pac. J. Optim."},{"issue":"1","key":"4_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10957-011-9871-x","volume":"151","author":"GM Fung","year":"2011","unstructured":"Fung, G.M., Mangasarian, O.L.: Equivalence of minimal $$\\ell _0$$- and $$\\ell _1$$-norm solutions of linear equalities, inequalities and linear programs for sufficiently small p. J. Optim. Theory Appl. 151(1), 1\u201310 (2011). https:\/\/doi.org\/10.1007\/s10957-011-9871-x","journal-title":"J. Optim. Theory Appl."},{"key":"4_CR17","unstructured":"Gamarnik, D., Zadik, I.: High dimensional regression with binary coefficients. estimating squared error and a phase transition. In: Proceedings of the 2017 Conference on Learning Theory. Proceedings of Machine Learning Research, vol. 65, pp. 948\u2013953. PMLR, 07\u201310 July 2017"},{"issue":"4","key":"4_CR18","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.1007\/s10898-012-9853-z","volume":"56","author":"J Gao","year":"2013","unstructured":"Gao, J., Li, D.: A polynomial case of the cardinality-constrained quadratic optimization problem. J. Glob. Optim. 56(4), 1441\u20131455 (2013). https:\/\/doi.org\/10.1007\/s10898-012-9853-z","journal-title":"J. Glob. Optim."},{"key":"4_CR19","doi-asserted-by":"publisher","unstructured":"Ge, D., Jiang, X., Ye, Y.: A note on the complexity of LP minimization. Math. Program. 129, 285\u2013299 (2011). https:\/\/doi.org\/10.1007\/s10107-011-0470-2","DOI":"10.1007\/s10107-011-0470-2"},{"issue":"6","key":"4_CR20","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1109\/JPROC.2010.2045092","volume":"98","author":"A Gilbert","year":"2010","unstructured":"Gilbert, A., Indyk, P.: Sparse recovery using sparse matrices. Proc. IEEE 98(6), 937\u2013947 (2010). https:\/\/doi.org\/10.1109\/JPROC.2010.2045092","journal-title":"Proc. IEEE"},{"key":"4_CR21","doi-asserted-by":"publisher","unstructured":"Gilbert, A.C., Muthukrishnan, S., Strauss, M.J.: Approximation of functions over redundant dictionaries using coherence. In: SODA, pp. 243\u2013252. Citeseer (2003). https:\/\/doi.org\/10.5555\/644108.644149","DOI":"10.5555\/644108.644149"},{"key":"4_CR22","series-title":"Advances in Intelligent Systems and Computing","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-319-18161-5_31","volume-title":"Modelling, Computation and Optimization in Information Systems and Management Sciences","author":"T Migot","year":"2015","unstructured":"Migot, T., Haddou, M.: A smoothing method for sparse optimization over polyhedral sets. In: Le Thi, H.A., Pham Dinh, T., Nguyen, N.T. (eds.) Modelling, Computation and Optimization in Information Systems and Management Sciences. AISC, vol. 359, pp. 369\u2013379. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-18161-5_31"},{"issue":"4","key":"4_CR23","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1080\/00401706.1967.10490502","volume":"9","author":"RR Hocking","year":"1967","unstructured":"Hocking, R.R., Leslie, R.N.: Selection of the best subset in regression analysis. Technometrics 9(4), 531\u2013540 (1967). https:\/\/doi.org\/10.1080\/00401706.1967.10490502","journal-title":"Technometrics"},{"issue":"1\u20134","key":"4_CR24","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1080\/02331939908844431","volume":"45","author":"O Mangasarian","year":"1999","unstructured":"Mangasarian, O.: Minimum-support solutions of polyhedral concave programs. Optimization 45(1\u20134), 149\u2013162 (1999). https:\/\/doi.org\/10.1080\/02331939908844431","journal-title":"Optimization"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Nesterov, Y., Nemirovski, A.: Interior-point polynomial algorithms in convex programming. In: SIAM Studies in Applied Mathematics (1994)","DOI":"10.1137\/1.9781611970791"},{"key":"4_CR26","unstructured":"Nguyen, T.: Dropping forward-backward algorithms for feature selection. CoRR abs\/1910.08007 (2019)"},{"key":"4_CR27","doi-asserted-by":"publisher","unstructured":"Oymak, S., Thrampoulidis, C., Hassibi, B.: The squared-error of generalized lasso: a precise analysis. In: 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 1002\u20131009 (2013). https:\/\/doi.org\/10.1109\/Allerton.2013.6736635","DOI":"10.1109\/Allerton.2013.6736635"},{"key":"4_CR28","doi-asserted-by":"publisher","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: Subset Selection by Pareto Optimization. NIPS 2015, pp. 1774\u20131782. MIT Press, Cambridge (2015). https:\/\/doi.org\/10.5555\/2969239.2969437","DOI":"10.5555\/2969239.2969437"},{"issue":"6","key":"4_CR29","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1080\/10556788.2010.511668","volume":"26","author":"F Rinaldi","year":"2011","unstructured":"Rinaldi, F.: Concave programming for finding sparse solutions to problems with convex constraints. Optim. Methods Softw. 26(6), 971\u2013992 (2011). https:\/\/doi.org\/10.1080\/10556788.2010.511668","journal-title":"Optim. Methods Softw."},{"key":"4_CR30","doi-asserted-by":"publisher","unstructured":"Rinaldi, F., Schoen, F.: Concave programming for minimizing the zero-norm over polyhedral sets. Comput. Optim. Appl. 46, 467\u2013486 (07 2010). https:\/\/doi.org\/10.1007\/s10589-008-9202-9","DOI":"10.1007\/s10589-008-9202-9"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Teng, Y., Qi, S., Xiao, D., Xu, L., Li, J., Kang, Y.: A general solution to least squares problems with box constraints and its applications. Math. Probl. Eng. 2016 (2016)","DOI":"10.1155\/2016\/3934872"},{"issue":"10","key":"4_CR32","doi-asserted-by":"publisher","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","volume":"50","author":"J Tropp","year":"2004","unstructured":"Tropp, J.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50(10), 2231\u20132242 (2004). https:\/\/doi.org\/10.1109\/TIT.2004.834793","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"4_CR33","doi-asserted-by":"publisher","first-page":"2183","DOI":"10.1109\/TIT.2009.2016018","volume":"55","author":"MJ Wainwright","year":"2009","unstructured":"Wainwright, M.J.: Sharp thresholds for high-dimensional and noisy sparsity recovery using $$\\ell _1$$-constrained quadratic programming (lasso). IEEE Trans. Inf. Theor. 55(5), 2183\u20132202 (2009). https:\/\/doi.org\/10.1109\/TIT.2009.2016018","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"52","key":"4_CR34","doi-asserted-by":"publisher","first-page":"33117","DOI":"10.1073\/pnas.2014241117","volume":"117","author":"J Zhu","year":"2020","unstructured":"Zhu, J., Wen, C., Zhu, J., Zhang, H., Wang, X.: A polynomial algorithm for best-subset selection problem. Proc. Natl. Acad. Sci. 117(52), 33117\u201333123 (2020). https:\/\/doi.org\/10.1073\/pnas.2014241117","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"14","key":"4_CR35","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1016\/j.ipl.2013.04.014","volume":"113","author":"A \u00c7ivril","year":"2013","unstructured":"\u00c7ivril, A.: A note on the hardness of sparse approximation. Inf. Process. Lett. 113(14), 543\u2013545 (2013). https:\/\/doi.org\/10.1016\/j.ipl.2013.04.014","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-32726-1_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,21]],"date-time":"2023-05-21T20:29:02Z","timestamp":1684700942000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-32726-1_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031327254","9783031327261"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-32726-1_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"22 May 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madison, WI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/optimization.discovery.wisc.edu\/ipco-2023-madison\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"119","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}