2

Let $x$ be an unknown real vector of size n.

Suppose we can find n vectors $v_i$, and are given the values $x^Tv_i$. Then we can simply solve for $x$ by Gauss or some other method and determine $x$ uniquely and precisely( iff $v_i$ are lin indep).

However, suppose now that we are only given the values $x^Tv_i$ up to some finite precision, then we might still find $x$, but also only up to a certain finite precision.

In the ideal infinite precision case, we would not gain anything by working with more than n vectors $v_i$, as we can already compute x uniquely. However, it seems that increasing n might help to determine $x$ with higher precision or maybe arbitrary precision even though the values $x^Tv_i$ have a fixed bounded precision. Of course this would be easy if we could freely choose the $v_i$, be just choosing very large values.

So suppose this is not possible. ie suppose that $v_i$ are given randomly and the norm of $v_i$ is bounded. What numerical methods are available, to determine x.

Assume that computation can be done with infinite precision

wood
  • 840

1 Answers1

2

Using more vectors (say, $m$) than the dimension of the space (say, $n$) means using a frame (as opposed to a basis). Your question is about the recovery from noisy frame coefficients.

Let $x_1,\dots,x_m$ be the frame vectors, and let $e_1,\dots e_n$ be a basis of $\mathbb R^n$. Then for each $j=1,\dots,n$ we have an $m$-dimensional vector vectors $(x_1^Te_j,\dots , x_m^Te_j)$. These vectors span the $n$-dimensional subspace $A$ in $\mathbb R^m$. The most basic idea (which seems to work well sometimes) is to orthogonally project your vector of noisy coefficients onto $A$, and reconstruct $x$ from this projection.

The book Frames and bases: an introductory course by Ole Christensen discusses this topic and gives references to the literature. A relevant subject is quantized frame expansions, in which the coefficients are subject to rounding. E.g., this paper.

ˈjuː.zɚ79365
  • 3,004