MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question
Defining $g(y)=0$ seems to satisfy your requirement, hence the answer to your question seems to be “no”. You seem to ask for a linear function that would annihilate the result of any noise-free measurement. I don't understand why you think this might solve the problem. Also, $g$ had better be defined on $\mathbb{R}^m$. Where did you want the range of $g$ to be? – Harald Hanche-Olsen Feb 9 '10 at 13:34
My answer below says that the using syndrome decoding is an efficient way of recovering $f$ provided that $f$ is sparse. – Victor Miller Feb 9 '10 at 17:14

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.

share|cite|improve this answer

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:

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.