Corruption and Recovery

Question

Suppose we want to recover an input vector $f \in \textbf{R}^n$ from some measurements $y = Af + \varepsilon$. Now $A$ is an $m \times n$ matrix and $\varepsilon$ are some unknown errors. Is this equivalent to finding some function $g: \textbf{R}^m \to \textbf{R}^m$ such that $g(Af+ \varepsilon) = g(Af) + g(\varepsilon) = g(\varepsilon)$?

In other words, we are considering the kernel of some unknown function $g(Af)$ so that we can identify the error term? Is syndrome decoding an efficient way of recovering $f$?

Answer 1

Take $B$ to be a "parity-check matrix", i.e. an $n \times (n-m)$ matrix with $BA=0$ which exists by linear algebra as long as $n > m$ (but maybe your $m$'s and $n$'s are mixed up, the input should be from a lower dimensional space then the code vector). So, putting $g(x) = Bx$ will have the property that $g(Af+\epsilon)=g(\epsilon)$ but $g$ takes values in $\mathbb{R}^{n-m}$. Now, syndrome decoding requires you to have, for each syndrome $s \in \mathbb{R}^{n-m}$ a choice of $v_s \in \mathbb{R}^n, Bv_s=s$ usually by minimizing the norm of $v_s$ among all choices. In your situation, $y-v_{g(\epsilon)}$ will be a codeword which, hopefully is $f$.

These things are not usually done in $\mathbb{R}^n$ because there is no good way to choose the $v_s$. If you work over a finite field, then it is possible for all $s$ to choose $v_s$ minimizing the Hamming norm and so maximizing the changes of correct decoding (assuming few errors in the Hamming norm). Now making this list of the $v_s$ for all $s$ is not efficient in the sense of complexity theory as there might be a lot of $s$'s. But, if you can afford the time to do it once and for all, then using the syndromes is an efficient way of decoding.

Answer 2

It sounds like you should investigate "Compressed Sensing". There has been a lot of activity in this area by Donoho and Tao (and others). Here is just a sample -- as to when you can recover your original $f$ via linear programming: http://arxiv.org/abs/math.MG/0502327

Here's the abstract

This paper considers the classical error correcting problem which is frequently discussed in coding theory. We wish to recover an input vector $f \in \mathbb{R}^n$ from corrupted measurements $y = A f + e$. Here, $A$ is an $m$ by $n$ (coding) matrix and $e$ is an arbitrary and unknown vector of errors. Is it possible to recover $f$ exactly from the data $y$? We prove that under suitable conditions on the coding matrix $A$, the input $f$ is the unique solution to the $\ell_1$-minimization problem $\min_{g \in \mathbb{R}^n} \| y - Ag \|_{\ell_1} $, where $\|x\|_{\ell_1} := \sum_i |x_i|$, provided that the support of the vector of errors is not too large, $\|e\|_{\ell_0} := | \{{ i : e_i \neq 0}\}| \le \rho \cdot m$ for some $\rho > 0$. In short, $f$ can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; $f$ is recovered exactly even in situations where a significant fraction of the output is corrupted.