RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Mat. Zametki, 2018, Volume 104, Issue 6, Pages 863–871 (Mi mz12167)  

On the Recovery of an Integer Vector from Linear Measurements

S. V. Konyagin

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow

Abstract: Let $1\le 2l\le m<d$. A vector $x\in\mathbb Z^d$ is said to be $l$-sparse if it has at most $l$ nonzero coordinates. Let an $m\times d$ matrix $A$ be given. The problem of the recovery of an $l$-sparse vector $x\in\mathbb Z^d$ from the vector $y=A x\in\mathbb R^m$ is considered. In the case $m=2l$, we obtain necessary and sufficient conditions on the numbers $m$, $d$, and $k$ ensuring the existence of an integer matrix $A$ all of whose elements do not exceed $k$ in absolute value which makes it possible to reconstruct $l$-sparse vectors in $\mathbb Z^d$. For a fixed $m$, these conditions on $d$ differ only by a logarithmic factor depending on $k$.

Keywords: nonsingular matrix, lattices, successive minima.

Funding Agency Grant Number
Russian Science Foundation 14-50-00005
This work was supported by the Russian Science Foundation under grant 14-50-00005.


DOI: https://doi.org/10.4213/mzm12167

Full text: PDF file (455 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Mathematical Notes, 2018, 104:6, 859–865

Bibliographic databases:

Document Type: Article
UDC: 512.643+519.21
PACS: 02.10.Yn, 02.30.Mv
Received: 29.08.2018

Citation: S. V. Konyagin, “On the Recovery of an Integer Vector from Linear Measurements”, Mat. Zametki, 104:6 (2018), 863–871; Math. Notes, 104:6 (2018), 859–865

Citation in format AMSBIB
\Bibitem{Kon18}
\by S.~V.~Konyagin
\paper On the Recovery of an Integer Vector from Linear Measurements
\jour Mat. Zametki
\yr 2018
\vol 104
\issue 6
\pages 863--871
\mathnet{http://mi.mathnet.ru/mz12167}
\crossref{https://doi.org/10.4213/mzm12167}
\elib{http://elibrary.ru/item.asp?id=36448726}
\transl
\jour Math. Notes
\yr 2018
\vol 104
\issue 6
\pages 859--865
\crossref{https://doi.org/10.1134/S0001434618110305}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000454546800030}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85059238215}


Linking options:
  • http://mi.mathnet.ru/eng/mz12167
  • https://doi.org/10.4213/mzm12167
  • http://mi.mathnet.ru/eng/mz/v104/i6/p863

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Related presentations:
  • Математические заметки Mathematical Notes
    Number of views:
    This page:118
    References:19
    First page:17

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019