I got over-determined linear equations system with M equations and N unknowns (M >> N, M is usually less than 100 while N comes to tens of thousads) in complex domain, in matrix notation:
Ax = b
where A is complex matrix with M rows and N columns and b is column vector with M rows.
The problem is to find such x that would minimize above equation with additional assumption that i have direct access ONLY to few consecutive rows of A (it would be computed on embedded system with limited memory) and the coefficients would arrive in column-row order (e.g. first row of A, then second, third and so on).
My question is:
Is there any iterative algorithm that would allow to compute subsequent approximations of x that would be convergent to "optimal" x value (in terms of least square) having access only to few adjacent rows of A matrix?
First attempts included:
- $A^T A x = A^T b \to x ~ (A^T A)^{-1} A^T b$ is already working, the problem was in lack of conjugate in transposition (in fact it should be $A^H A x = A^H b \to x ~ (A^H A)^{-1} A^H b$ ) - however, random access to whole A matrix is required.
- QR decomposition with Givens rotation - worked like a charm but requires column-wise access to A.
Best regards and thanks in advance :) !
After writing down $A^TA$ it turned out that each result element - computed as dot product of one row of $A^T$ and one column of $A$ - contains sum of products, where each product contains elements from single row of $A$, and so that it is possible to compute $A^TA$ processing only single row at a time. Thanks for any comments and best regards :)