{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:16:37Z","timestamp":1781345797724,"version":"3.54.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T00:00:00Z","timestamp":1620086400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T00:00:00Z","timestamp":1620086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1818969"],"award-info":[{"award-number":["1818969"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["413995221"],"award-info":[{"award-number":["413995221"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm of the vector. Our main results are new improved bounds on the minimal<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm of solutions to systems<jats:inline-formula><jats:alternatives><jats:tex-math>$$A\\varvec{x}=\\varvec{b}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>A<\/mml:mi><mml:mrow><mml:mi>x<\/mml:mi><\/mml:mrow><mml:mo>=<\/mml:mo><mml:mrow><mml:mi>b<\/mml:mi><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where<jats:inline-formula><jats:alternatives><jats:tex-math>$$A\\in \\mathbb {Z}^{m\\times n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>A<\/mml:mi><mml:mo>\u2208<\/mml:mo><mml:msup><mml:mrow><mml:mi>Z<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi>m<\/mml:mi><mml:mo>\u00d7<\/mml:mo><mml:mi>n<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>,<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\varvec{b}}\\in \\mathbb {Z}^m$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mrow><mml:mi>b<\/mml:mi><\/mml:mrow><mml:mo>\u2208<\/mml:mo><mml:msup><mml:mrow><mml:mi>Z<\/mml:mi><\/mml:mrow><mml:mi>m<\/mml:mi><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{x}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>x<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell _0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u2113<\/mml:mi><mml:mn>0<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>R<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, to other subdomains such as<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Z}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>Z<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.<\/jats:p>","DOI":"10.1007\/s10107-021-01657-8","type":"journal-article","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:03:56Z","timestamp":1620129836000},"page":"519-546","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Sparse representation of vectors in lattices and semigroups"],"prefix":"10.1007","volume":"192","author":[{"given":"Iskander","family":"Aliev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gennadiy","family":"Averkov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jes\u00fas A.","family":"De Loera","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5720-8978","authenticated-orcid":false,"given":"Timm","family":"Oertel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"1657_CR1","doi-asserted-by":"crossref","unstructured":"Aliev, I., Averkov, G., De\u00a0Loera, J.A., Oertel, T.: Optimizing sparsity over lattices and semigroups. In: Integer Programming and Combinatorial Optimization, Volume 12125 of Lecture Notes in Comput. Sci., pp. 40\u201351. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-45771-6_4"},{"issue":"3","key":"1657_CR2","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1137\/17M1162792","volume":"28","author":"I Aliev","year":"2018","unstructured":"Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Weismantel, R.: The support of integer optimal solutions. SIAM J. Optim. 28(3), 2152\u20132157 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1657_CR3","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1137\/16M1083876","volume":"1","author":"I Aliev","year":"2017","unstructured":"Aliev, I., De Loera, J.A., Oertel, T., O\u2019Neill, C.: Sparse solutions of linear diophantine equations. SIAM J. Appl. Algebra Geom. 1(1), 239\u2013253 (2017)","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"1657_CR4","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.laa.2020.10.027","volume":"611","author":"G Averkov","year":"2021","unstructured":"Averkov, G., Chavez, A., De Loera, J.A., Gillespie, B.: The lattice of cycles of an undirected graph. Linear Algebra Appl. 611, 213\u2013236 (2021)","journal-title":"Linear Algebra Appl."},{"key":"1657_CR5","unstructured":"Baldoni, V., Berline, N., De\u00a0Loera, J., Dutra, B., K\u00f6ppe, M., Moreinis, S., Pinto, G., Vergne, M., Wu, J.: A User\u2019s Guide for LattE Integrale v1.7.2 (2014). http:\/\/www.math.ucdavis.edu\/~latte\/"},{"key":"1657_CR6","volume-title":"A Course in Convexity. Graduate Studies in Mathematics","author":"AI Barvinok","year":"2002","unstructured":"Barvinok, A.I.: A Course in Convexity. Graduate Studies in Mathematics, vol. 54. American Mathematical Society, Providence (2002)"},{"key":"1657_CR7","unstructured":"Barvinok, A.I., Pommersheim, J.E.: An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996\u201397), Volume\u00a038 of Math. Sci. Res. Inst. Publ., pp. 91\u2013147. Cambridge Univ. Press, Cambridge (1999)"},{"issue":"4","key":"1657_CR8","first-page":"957","volume":"16","author":"AI Barvinok","year":"2003","unstructured":"Barvinok, A.I., Woods, K.: Short rational generating functions for lattice point problems. J. AMS 16(4), 957\u2013979 (2003)","journal-title":"J. AMS"},{"key":"1657_CR9","doi-asserted-by":"crossref","unstructured":"Boche, H., Calderbank, R., Kutyniok, G., Vyb\u00edral, J.: A survey of compressed sensing. In: Compressed Sensing and Its Applications, Appl. Numer. Harmon. Anal., pp. 1\u201339. Birkh\u00e4user\/Springer, Cham (2015)","DOI":"10.1007\/978-3-319-16042-9_1"},{"key":"1657_CR10","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E., Rudelson, M., Tao, T., Vershynin, R.: Error correction via linear programming. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 668\u2013681 (2005)","DOI":"10.1109\/SFCS.2005.5464411"},{"issue":"8","key":"1657_CR11","doi-asserted-by":"publisher","first-page":"1207","DOI":"10.1002\/cpa.20124","volume":"59","author":"EJ Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Commun. Pure Appl. Math."},{"issue":"12","key":"1657_CR12","doi-asserted-by":"publisher","first-page":"4203","DOI":"10.1109\/TIT.2005.858979","volume":"51","author":"EJ Cand\u00e8s","year":"2005","unstructured":"Cand\u00e8s, E.J., Tao, T.: Decoding by linear programming. IEEE Trans. Inform. Theory 51(12), 4203\u20134215 (2005)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"10","key":"1657_CR13","doi-asserted-by":"publisher","first-page":"972","DOI":"10.4169\/amer.math.monthly.122.10.972","volume":"122","author":"SM Cioab\u0103","year":"2015","unstructured":"Cioab\u0103, S.M., Cameron, P.J.: A graph partition problem. Am. Math. Mon. 122(10), 972\u2013982 (2015)","journal-title":"Am. Math. Mon."},{"issue":"4","key":"1657_CR14","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1016\/j.jsc.2003.04.003","volume":"38","author":"JA De Loera","year":"2004","unstructured":"De Loera, J.A., Hemmecke, R., Tauzer, J., Yoshida, R.: Effective lattice point counting in rational convex polytopes. J. Symb. Comput. 38(4), 1273\u20131302 (2004)","journal-title":"J. Symb. Comput."},{"key":"1657_CR15","volume-title":"Abstract Algebra","author":"DS Dummit","year":"2004","unstructured":"Dummit, D.S., Foote, R.M.: Abstract Algebra, 3rd edn. Wiley, New York (2004)","edition":"3"},{"issue":"5","key":"1657_CR16","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.orl.2005.09.008","volume":"34","author":"F Eisenbrand","year":"2006","unstructured":"Eisenbrand, F., Shmonin, G.: Carath\u00e9odory bounds for integer cones. Oper. Res. Lett. 34(5), 564\u2013568 (2006)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1657_CR17","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1016\/j.acha.2016.12.004","volume":"45","author":"A Flinth","year":"2018","unstructured":"Flinth, A., Kutyniok, G.: PROMP: a sparse recovery approach to lattice-valued signals. Appl. Comput. Harmon. Anal. 45(3), 668\u2013708 (2018)","journal-title":"Appl. Comput. Harmon. Anal."},{"key":"1657_CR18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.amc.2018.08.007","volume":"340","author":"L Fukshansky","year":"2019","unstructured":"Fukshansky, L., Needell, D., Sudakov, B.: An algebraic perspective on integer sparse recovery. Appl. Math. Comput. 340, 31\u201342 (2019)","journal-title":"Appl. Math. Comput."},{"key":"1657_CR19","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)"},{"key":"1657_CR20","doi-asserted-by":"publisher","DOI":"10.1201\/9781420003208","volume-title":"Non-Unique Factorizations: Algebraic, Combinatorial and Analytic Theory. Pure and Applied Mathematics","author":"A Geroldinger","year":"2006","unstructured":"Geroldinger, A., Halter-Koch, F.: Non-Unique Factorizations: Algebraic, Combinatorial and Analytic Theory. Pure and Applied Mathematics. Chapman and Hall\/CRC, Boca Raton (2006)"},{"key":"1657_CR21","unstructured":"Gruber, P.M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland Mathematical Library, vol. 37, 2nd edn. North-Holland Publishing Co., Amsterdam (1987)"},{"issue":"3","key":"1657_CR22","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/3242953.3242964","volume":"5","author":"C Haase","year":"2018","unstructured":"Haase, C.: A survival guide to Presburger arithmetic. ACM SIGLOG News 5(3), 67\u201382 (2018)","journal-title":"ACM SIGLOG News"},{"key":"1657_CR23","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780199219858.001.0001","volume-title":"An Introduction to the Theory of Numbers. Oxford Mathematics","author":"GH Hardy","year":"2008","unstructured":"Hardy, G.H., Wright, E.M., Heath-Brown, R., Silverman, J.: An Introduction to the Theory of Numbers. Oxford Mathematics. OUP, Oxford (2008)"},{"issue":"6","key":"1657_CR24","doi-asserted-by":"publisher","first-page":"863","DOI":"10.4213\/mzm12167","volume":"104","author":"SV Konyagin","year":"2018","unstructured":"Konyagin, S.V.: On the recovery of an integer vector from linear measurements. Mat. Zametki 104(6), 863\u2013871 (2018)","journal-title":"Mat. Zametki"},{"issue":"2","key":"1657_CR25","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0095-8956(87)90021-9","volume":"43","author":"L Lov\u00e1sz","year":"1987","unstructured":"Lov\u00e1sz, L.: Matching structure and the matching lattice. J. Comb. Theory Ser. B 43(2), 187\u2013222 (1987)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"1657_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539792240406","volume":"24","author":"BK Natarajan","year":"1995","unstructured":"Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2), 227\u2013234 (1995)","journal-title":"SIAM J. Comput."},{"key":"1657_CR27","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Pak, I.: Complexity of short Presburger arithmetic. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 812\u2013820 (2017)","DOI":"10.1145\/3055399.3055435"},{"key":"1657_CR28","doi-asserted-by":"crossref","unstructured":"Nguyen, D., Pak, I.: Short Presburger arithmetic is hard. SIAM J. Computi., (0):STOC17\u20131 (2019)","DOI":"10.1137\/17M1151146"},{"key":"1657_CR29","doi-asserted-by":"crossref","unstructured":"Oertel, T., Paat, J., Weismantel, R.: Sparsity of integer solutions in the average case. In: Integer Programming and Combinatorial Optimization, Volume 11480 of Lecture Notes in Comput. Sci., pp. 341\u2013353. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-17953-3_26"},{"issue":"3","key":"1657_CR30","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/19M1275954","volume":"4","author":"T Oertel","year":"2020","unstructured":"Oertel, T., Paat, J., Weismantel, R.: The distributions of functions related to parametric integer optimization. SIAM J. Appl. Algebra Geom. 4(3), 422\u2013440 (2020)","journal-title":"SIAM J. Appl. Algebra Geom."},{"issue":"2","key":"1657_CR31","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1109\/TSP.2013.2289875","volume":"62","author":"M Rossi","year":"2014","unstructured":"Rossi, M., Haimovich, A.M., Eldar, Y.C.: Spatial compressive sensing for MIMO radar. IEEE Trans. Signal Process. 62(2), 419\u2013430 (2014)","journal-title":"IEEE Trans. Signal Process."},{"key":"1657_CR32","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986). A Wiley-Interscience Publication"},{"issue":"2","key":"1657_CR33","doi-asserted-by":"publisher","first-page":"543","DOI":"10.2140\/pjm.1979.83.543","volume":"83","author":"JD Vaaler","year":"1979","unstructured":"Vaaler, J.D.: A geometric inequality with applications to linear forms. Pac. J. Math. 83(2), 543\u2013553 (1979)","journal-title":"Pac. J. Math."},{"issue":"2","key":"1657_CR34","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1017\/jsl.2015.4","volume":"80","author":"K Woods","year":"2015","unstructured":"Woods, K.: Presburger arithmetic, rational generating functions, and quasi-polynomials. J. Symb. Log. 80(2), 433\u2013449 (2015)","journal-title":"J. Symb. Log."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01657-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01657-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01657-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T04:31:16Z","timestamp":1724992276000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01657-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,4]]},"references-count":34,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1657"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01657-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,4]]},"assertion":[{"value":"30 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}