How does one recover the true solution to underdetermined equations when one has some prior or data about how the solution should look like?

Question

I was interested in recovering the solution $x$ to a linear system underdetermined $N < D$:

$$ Ax = y$$

as accurately as possible to the true $x$. Obviously, this system has infinite number of solutions, therefore one has to constrain the optimization search or bias it in some way such that the solution one is looking for comes out. For example, if one has a prior that $x$ is sparse, there are well known algorithms like LASSO, orthogonal matching persuit etc to find such a $x$ (chapter 4 of Sparse recovery http://people.csail.mit.edu/moitra/docs/bookex.pdf).

However, I was wondering, if we do know $A$, $y$ and some prior on $x$ (and possibly some noisy versions of $x$), is it possible to obtain a good estimate for the true value for $x$ that is close to the truth $x^*$ and that is robust to noise to some degree?

For example, if $x$ has the shape of a Gaussian, it would be nice to be able to obtain $x$'s that are shaped like that even if the new $y=A x_{new}$ might have a different mean, std or even noise.

In an even harder scenario were the parametric form might not be known but just some examples of the $x$'s that show the prototypical shape of $x$. Is there any methods to solve problems of this sort?

I am aware this might be quite different from standard machine learning or statistical learning theory since those fields are usually more interested in finding minimizers to the expected risk $E[l(f(x),y)]$ rather than finding exactly the minimizer $f(x)$.

Anyway, any pointers to potential research that has been done would be useful, if none, its also good to know!

---

As a clarification, I don't mean x is normally distributed, I mean literally $x=f(a)$ is an RBF. The issue is because there is an infinite number of solutions, how do I force my system to choose the RBF shaped one or the one shaped according to the natural signal of the problem?

---

related question posted a month ago: How does one design regularizers such that they match the parameters that generated the data when one has strong priors about the parameters?

Answer 1

For example, if $x$ has the shape of a Gaussian, it would be nice to be able to obtain $x$'s that are shaped like that even if the new $y=A x_{new}$ might have a different mean, std or even noise.

That's the idea of MAP (Maximum A Posteriori) estimation.

For general phenomenon see how MAP relates to regularization.

MAP is like MLE for such a situation (where you have a prior on $x$).

---

Let's get concrete and take a look at linear regression.

Square error comes from MLE for the model where $$y = X\beta + \epsilon$$ where $\epsilon$ follows Normal(0, $\sigma^2$) (we assume some fixed variance).

Remember in MLE $$\hat{\beta} = \arg\max_{\beta} P(y|X;\beta)$$.

In this model $$P(y|X; \beta) = c_{\sigma} e^{-\frac{(X\beta - y)^2}{2\sigma^2}}$$

So $$\arg\max_{\beta} \log(P(y|X; \beta)) = \arg\min_{\beta} -\log(P(y|X; \beta))$$ $$= \arg\min_{\beta}(\frac{(X\beta - y)^2}{2\sigma^2} + \log(c_{\sigma})) = \arg\min_{\beta} (X\beta - y)^2 $$.

To summarize, $\hat{\beta} = \arg\min_{\beta} (X\beta - y)^2$

MAP

In MAP you take $\hat{\beta} = \arg\min_{\beta} P(\beta |y)$

If you also assume Normal(0, $\frac{1}{\lambda}$) distribution on $\beta$ then you might incorporate this knowledge since

$$P(\beta |y; X) = \frac{P(y | \beta; X) P(\beta)}{P(y; X)} \propto P(y | \beta; X) P(\beta)$$

In linear regression case after taking log

$$\arg\max_{\beta} \log(P(\beta |y; X)) = \arg\min_{\beta} -\log(P(\beta |y; X))$$ $$= \arg\min_{\beta} - \log(P(y | \beta; X) P(\beta)) = \arg\min_{\beta}({(X\beta - y)^2} + \frac{\lambda}{\sigma^2} \beta^2)$$

So, after all, $\hat{\beta} = \arg\min_{\beta}({(X\beta - y)^2} + \frac{\lambda}{\sigma^2} \beta^2)$

---

What this means?

We assumed Gaussian prior, and came up with Ridge regression! You can also retrieve LASSO analogously, but you'd need to impose Laplace prior.

For a related question (the one about robustness) you can also check out Bishop's Training with Noise is Equivalent to Tikhonov regularization.