IJPAM: Volume 57, No. 2 (2009)

LOW-DIMENSIONAL LINEAR CODES WITH HIGH
BREAKDOWN POINTS BY QR DECOMPOSITION

Ryuichi Ashino

, Truong Nguyen-Ba

, Rémi Vaillancourt

Department of Mathematical Sciences
Osaka Kyoiku University
Osaka, 582-8582, JAPAN
e-mail: [email protected]
$^{2,3}$ Department of Mathematics and Statistics
University of Ottawa
585, King Edward Ave., Ottawa, Ontario, K1N 6N5, CANADA

e-mail: [email protected]

Abstract.Decoding linear codes by $\ell_1$ linear programming consists in recovering an input vector $x\in\mathbb{R}^n$ from corrupted oversampled measurements where $A\in\mathbb{R}^{m\times n}$ is a full rank matrix with and $z\in\mathbb{R}^{m}$ is a sparse vector. Appropriate random matrices $A\in\mathbb{R}^{2pn\times n}$ are empirically constructed by stacking the ``signed'' inverses of $n\times n$ partitions of the QR decomposition of random matrices $M\in\mathbb{R}^{2pn\times n}$ uniformly distributed so that the vector can be recovered numerically to an error smaller than $10^{-5}$ , provided the corrupting vector is sufficiently sparse. Numerical results on the mean of the number of zero components in at breakdown points are obtained for and . Other less effective matrices are presented and comparison is made with Donoho's theoretical results based on neighborly polytopes. A corrupted image is decoded and applications to cryptography are mentioned.