Date(s) : 13/11/2014 iCal
11 h 00 min - 12 h 00 min
Compressed sensing (CS) attracted a lot of attention in last few years, starting from first papers published in 2006. Nevertheless a discrete 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 talk can be considered as a report on what was done in the direction of discrete CS during this year.
Discrete CS problem can be stated in the following way – to find linear code C and its parity-check matrix H such that an error vector e of Hamming weight T or less can be recovered from the syndrome 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 problem on 20 questions.
In the talk we give a solution of discrete CS problem in the same way as RS-codes provide the solution of main problem of coding 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 experimantal et analytique sur les lois del Dilatabilite de fluides » J. de Ecole Polytechnique 1, pp.24-76, 1795 and M.T. Comer, E.L. Kaltofen, C.Pernet, « Sparse Polynomial Interpolationb and Berlekamp-Massey Algorithms That Correct Outlier Errors in Input Values », in Proc. ISSAC 2011, pp. 138-145. The optimal solution, which will be described in the talk, uses redundancy only 2(T+L).
–
In the conclusion it will be shown how these results can be applied for a limited version of ordinary CS problem.
–
The talk is based on joint research of the speaker with Serge Vladuts, Cedric Tavernier and Valery Lomakov.
–
Grigory Kabatiansky, Skolkovo Institute of Science and Technology
Catégories