Assume that we want to solve this linear system:
$$A^TA x = b$$
Matrix $A$ is square and random integer of 8-bit, e.g numbers between 0 and 255. Vector $b$ is known as well and also integer of 8-bit. Same for vector $x$.
So now to my question: What is the best way to solve a linear system if the matrix $A$ is square, integer and 8-bit? It must be safe to do this. I cannot handle a system that are non-invertible. Also $A$ contains noise as well.
- Backward substitution
- Cholesky decomposition
- LU decomposition
- QR decomposition
- SVD decomposition
Your question seems to be non-sense. Let $U=\{0..255\}\subset \mathbb{N}$.
You want to solve in $x\in U^n$ (or, at least, obtain an approximation of $x$ -by modifying $A$-) the equation $Bx=b$ where $B=A^TA$, $A\in M_n(U),b\in U^n$ are known. Assume, in the sequel, that $n=10$.
Unfortunately, all the entries of $B$ are -in general- $>50000$ and the entries of $b$ are $<256$. Then the best approximation for $x$ is always $\tilde{x}=0$.
EDIT. Answer to the OP.
If you want a valid method for all $n$, you must assume that the $x_i$ are non-negative REALS, possibly bounded by $255$. We can use a least squre method.
I use the library NLPSolve (under Maple) "The NLPSolve command uses various methods implemented in a built-in library provided by the Numerical Algorithms Group (NAG)".
NLPSolve is an iteration method that gives (theoretically) the minimum of a non-linear function $f(x)$ under constraints of equality or inequality linking the variables $x_i$. Unfortunately, often we obtain only local minima...
Here we choose $f(x)=tr((Bx-b)^T(Bx-b))$ and the constraint $K$ is $\{x_i\leq 255\}$. The initial point is $L=\{0,\cdots,0\}$.
For $n=10$, we obtain solutions $\tilde{x}$ that are close to $(0,\cdots,0)$, for example
Note that the mean of $\dfrac{||B\tilde{x}-b||}{||b||}$ is $\approx 0.5$.