RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






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


Diskr. Mat., 2017, Volume 29, Issue 1, Pages 3–9 (Mi dm1401)  

Solving systems of linear Boolean equations with noisy right-hand sides over the reals

E. K. Alekseev, I. B. Oshkin, V. O. Popov, S. V. Smyshlyaev

ООО «Крипто-Про»

Abstract: The paper is concerned with the problem of solution of a system of linear equations with noisy right-hand side in the following setting: one knows a random $m\times N$-matrix $A$ with entries from $\{-1,1\}$ and a vector $xA+\xi\in \R^N$, where $\xi$ is the noise vector from $\R^N$, whose entries are independent realizations of a normally distributed random variable with parameters $0$ and $\sigma^2$, and $x$ is a random vector with coordinates from $\{-1,1\}$. The sought-for parameter is the vector $x$. We propose a method for constructing a set containing the sought-for vector with probability not smaller than the given one and estimate the cardinality of this set. Theoretical calculations of the parameters of the method are illustrated by experiments demonstrating the practical implementability of the method for cases when direct enumeration of all possible values of $x$ is unfeasible.

Keywords: system of linear equations with noisy right-hand side, additive Gaussian noise.

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

Full text: PDF file (426 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2018, 28:1, 1–5

Bibliographic databases:

UDC: 519.719.2+519.233
Received: 30.06.2016
Revised: 30.11.2016

Citation: E. K. Alekseev, I. B. Oshkin, V. O. Popov, S. V. Smyshlyaev, “Solving systems of linear Boolean equations with noisy right-hand sides over the reals”, Diskr. Mat., 29:1 (2017), 3–9; Discrete Math. Appl., 28:1 (2018), 1–5

Citation in format AMSBIB
\Bibitem{AleOshPop17}
\by E.~K.~Alekseev, I.~B.~Oshkin, V.~O.~Popov, S.~V.~Smyshlyaev
\paper Solving systems of linear Boolean equations with noisy right-hand sides over the reals
\jour Diskr. Mat.
\yr 2017
\vol 29
\issue 1
\pages 3--9
\mathnet{http://mi.mathnet.ru/dm1401}
\crossref{https://doi.org/10.4213/dm1401}
\elib{http://elibrary.ru/item.asp?id=28405131}
\transl
\jour Discrete Math. Appl.
\yr 2018
\vol 28
\issue 1
\pages 1--5
\crossref{https://doi.org/10.1515/dma-2018-0001}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000425893900001}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85054995783}


Linking options:
  • http://mi.mathnet.ru/eng/dm1401
  • https://doi.org/10.4213/dm1401
  • http://mi.mathnet.ru/eng/dm/v29/i1/p3

    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
  • Дискретная математика
    Number of views:
    This page:480
    Full text:18
    References:48
    First page:64

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