BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//6.4.6.4.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:3532@test.i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20141113T110000
DTEND;TZID=Europe/Paris:20141113T120000
DTSTAMP:20200827T115049Z
URL:https://test.i2m.univ-amu.fr/events/discrete-compressed-sensing-as-cod
ing-theory-problem/
SUMMARY:Discrete compressed sensing as coding theory problem - Grigory Kaba
tiansky
DESCRIPTION:Compressed sensing (CS) attracted a lot of attention in last fe
w years\, starting from first papers published in 2006. Nevertheless a dis
crete version of CS was not even stated properly until last year\, when in
a joint paper of Serge Vladuts and the speaker the corresponding problem
have been formulated and first results have been obtained (G.Kabatiansky\,
S.Vladuts\, "What to do if syndromes are corrupted also"\, in Proc. Int.
Workshop Optimal Codes\, Albena\, Bulgaria\, 2013). In some sense this tal
k can be considered as a report on what was done in the direction of discr
ete CS during this year.\nDiscrete CS problem can be stated in the followi
ng way – to find linear code C and its parity-check matrix H such that a
n error vector e of Hamming weight T or less can be recovered from the syn
drome equation He=s even if the syndrome s is given with L or less errors.
A particular case of this problem is for instance famous Erdosh-Ulam prob
lem on 20 questions.\nIn the talk we give a solution of discrete CS proble
m in the same way as RS-codes provide the solution of main problem of codi
ng theory for the cases when code length is at most field cardinality. It
is worth to remark that RS codes aren’t good for discrete CS problem as
they demand the redundancy at least 4TL\, see R.Prony\, ``Essai experimant
al et analytique sur les lois del Dilatabilite de fluides'' J. de Ecole Po
lytechnique 1\, pp.24-76\, 1795 and M.T. Comer\, E.L. Kaltofen\, C.Pernet\
, "Sparse Polynomial Interpolationb and Berlekamp-Massey Algorithms That C
orrect Outlier Errors in Input Values"\, in Proc. ISSAC 2011\, pp. 138-145
. The optimal solution\, which will be described in the talk\, uses redund
ancy only 2(T+L).\n-\nIn the conclusion it will be shown how these results
can be applied for a limited version of ordinary CS problem.\n-\nThe talk
is based on joint research of the speaker with Serge Vladuts\, Cedric Tav
ernier and Valery Lomakov.\n-\nGrigory Kabatiansky\, Skolkovo Institute of
Science and Technology\n\n
CATEGORIES:Séminaire Arithmétique et Théorie de l’Information (ATI)
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20141026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR