{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T19:50:04Z","timestamp":1773085804654,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T00:00:00Z","timestamp":1663027200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T00:00:00Z","timestamp":1663027200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The paper considers the problem of unique recovery of sparse finite-valued integer signals using a single linear integer measurement. For <jats:italic>l<\/jats:italic>-sparse signals in <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {Z}}^n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mrow>\n                      <mml:mi>Z<\/mml:mi>\n                    <\/mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$2l&lt;n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, with absolute entries bounded by <jats:italic>r<\/jats:italic>, we construct an <jats:inline-formula><jats:alternatives><jats:tex-math>$$1\\times n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> measurement matrix with maximum absolute entry <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta =O(r^{2l-1})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>l<\/mml:mi>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Here the implicit constant depends on <jats:italic>l<\/jats:italic> and <jats:italic>n<\/jats:italic> and the exponent <jats:inline-formula><jats:alternatives><jats:tex-math>$$2l-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>l<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is optimal. Additionally, we show that, in the above setting, a single measurement can be replaced by several measurements with absolute entries sub-linear in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The proofs make use of results on admissible <jats:inline-formula><jats:alternatives><jats:tex-math>$$(n-1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-dimensional integer lattices for <jats:italic>m<\/jats:italic>-sparse <jats:italic>n<\/jats:italic>-cubes that are of independent interest.<\/jats:p>","DOI":"10.1007\/s11590-022-01927-0","type":"journal-article","created":{"date-parts":[[2022,9,13]],"date-time":"2022-09-13T05:07:27Z","timestamp":1663045647000},"page":"739-751","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On unique recovery of finite-valued integer signals and admissible lattices of sparse hypercubes"],"prefix":"10.1007","volume":"17","author":[{"given":"Abdullah","family":"Alasmari","sequence":"first","affiliation":[]},{"given":"Iskander","family":"Aliev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,13]]},"reference":[{"issue":"1\u20133","key":"1927_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00454-008-9059-9","volume":"39","author":"I Aliev","year":"2008","unstructured":"Aliev, I.: Siegel\u2019s lemma and sum-distinct sets. Discrete Comput. Geom. 39(1\u20133), 59\u201366 (2008)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1927_CR2","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00605-004-0267-y","volume":"144","author":"I Aliev","year":"2005","unstructured":"Aliev, I., Schinzel, A., Schmidt, W.M.: On vectors whose span contains a given linear subspace. Monatsh. Math. 144(3), 177\u2013191 (2005)","journal-title":"Monatsh. Math."},{"key":"1927_CR3","first-page":"A167","volume":"17","author":"JM Anthonisse","year":"1973","unstructured":"Anthonisse, J.M.: A note on equivalent systems of linear Diophantine equations. Z. Operations Res. Ser. A-B 17, A167\u2013A177 (1973)","journal-title":"Z. Operations Res. Ser. A-B"},{"issue":"1","key":"1927_CR4","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF01393823","volume":"73","author":"E Bombieri","year":"1983","unstructured":"Bombieri, E., Vaaler, J.: On Siegel\u2019s lemma. Invent. Math. 73(1), 11\u201332 (1983)","journal-title":"Invent. Math."},{"issue":"8","key":"1927_CR5","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. Common. Pure Appl. Math. 59(8), 1207\u20131223 (2006)","journal-title":"Common. Pure Appl. Math."},{"issue":"12","key":"1927_CR6","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"},{"key":"1927_CR7","volume-title":"An Introduction to the Geometry of Numbers","author":"JWS Cassels","year":"1971","unstructured":"Cassels, J.W.S.: An Introduction to the Geometry of Numbers. Springer, Berlin (1971)"},{"key":"1927_CR8","doi-asserted-by":"crossref","unstructured":"Fukshansky, L., Hsu. A.: Covering point-sets with parallel hyperplanes and sparse signal recovery. Discrete and Computational Geometry (2022)","DOI":"10.1007\/s00454-022-00375-y"},{"key":"1927_CR9","first-page":"31","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":"1927_CR10","volume-title":"Geometry of Numbers. North-Holland Mathematical Library","author":"PM Gruber","year":"1987","unstructured":"Gruber, P.M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland Mathematical Library, vol. 37, 2nd edn. North-Holland Publishing Co, Amsterdam (1987)","edition":"2"},{"key":"1927_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.laa.2019.10.005","volume":"586","author":"S Konyagin","year":"2020","unstructured":"Konyagin, S., Sudakov, B.: An extremal problem for integer sparse recovery. Linear Algebra Appl. 586, 1\u20136 (2020)","journal-title":"Linear Algebra Appl."},{"issue":"6","key":"1927_CR12","doi-asserted-by":"crossref","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"},{"key":"1927_CR13","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.dam.2019.02.014","volume":"262","author":"P-L Poirion","year":"2019","unstructured":"Poirion, P.-L.: Optimal constraints aggregation method for ILP. Discrete Appl. Math. 262, 148\u2013157 (2019)","journal-title":"Discrete Appl. Math."},{"key":"1927_CR14","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1112\/jlms\/s1-28.3.309","volume":"28","author":"RA Rankin","year":"1953","unstructured":"Rankin, R.A.: On positive definite quadratic forms. J. Lond. Math. Soc. 28, 309\u2013314 (1953)","journal-title":"J. Lond. Math. Soc."},{"key":"1927_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0012-365X(74)90126-5","volume":"10","author":"IG Rosenberg","year":"1974","unstructured":"Rosenberg, I.G.: Aggregation of equations in integer programming. Discrete Math. 10, 325\u2013341 (1974)","journal-title":"Discrete Math."},{"issue":"6(450)","key":"1927_CR16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.4213\/rm9903","volume":"74","author":"KS Ryutin","year":"2019","unstructured":"Ryutin, K.S.: Recovering sparse integer vectors from linear measurements. Uspekhi Mat. Nauk 74(6(450)), 167\u2013168 (2019)","journal-title":"Uspekhi Mat. Nauk"},{"issue":"1","key":"1927_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.5802\/jtnb.712","volume":"22","author":"K Sawatani","year":"2010","unstructured":"Sawatani, K., Watanabe, T., Okuda, K.: A note on the Hermite\u2013Rankin constant. J. Th\u00e9or. Nombres Bordeaux 22(1), 209\u2013217 (2010)","journal-title":"J. Th\u00e9or. Nombres Bordeaux"},{"key":"1927_CR18","doi-asserted-by":"crossref","unstructured":"Schmidt, W.M.: Diophantine Approximations and Diophantine Equations. Lecture Notes in Mathematics. Springer, Berlin (1991)","DOI":"10.1007\/BFb0098246"},{"issue":"2","key":"1927_CR19","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1307\/mmj\/1030132184","volume":"45","author":"JL Thunder","year":"1998","unstructured":"Thunder, J.L.: Higher-dimensional analogs of Hermite\u2019s constant. Mich. Math. J. 45(2), 301\u2013314 (1998)","journal-title":"Mich. Math. J."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01927-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01927-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01927-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T12:17:17Z","timestamp":1678277837000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01927-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,13]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["1927"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01927-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,13]]},"assertion":[{"value":"16 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article. Data sharing not applicable to this article as no datasets were generated or analysed during the current study.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}