The fastest way to solve the least square for an overdetermined system

Question

I have a matrix A of size m * n (m of order ~ 100K and n ~ 500) and a vector b. In addition, my matrix is ​​poorly conditioned and has a drawback. Now I want to find the least square solution for Ax = b, and for this purpose I have compared some of the methods:

• scipy.linalg.lstsq (time / residual): 14s, 626.982
  
• scipy.sparse.linalg.lsmr (time / residual value): 4.5 s, 626.982 (same accuracy)
  

Now I have noticed that when I do not have a rank-deficient case that forms a normal equation and solves it using choles factorization, this is the fastest way to solve my problem. So my question is that if I am not interested in the solution of the minimum norm, is there a way to get the solution (any) in (A ^ TAx = b) when A ^ TA is singular. I tried scipy.linalg.solve, but it gives a LinAlgError for singular matrices. I would also like to know if A is such that m → n, poorly specified, perhaps not a complete col-rank, then which method should be used in terms of time, residual accuracy (or any other metric). Any thoughts and help are appreciated. Thank!

Answer 1

I would say that the “right” way is to use SVD, look at your singular range of values ​​and find out how many special values ​​you want to keep, i.e. find out how close you want A^T xfor b. Something like that:

def svd_solve(a, b):
    [U, s, Vt] = la.svd(a, full_matrices=False)
    r = max(np.where(s >= 1e-12)[0])
    temp = np.dot(U[:, :r].T, b) / s[:r]
    return np.dot(Vt[:r, :].T, temp)

However, for a size matrix (100000, 500)this will be too slow. I would recommend implementing the least squares yourself and adding a little regularization to avoid the appearance of a single matrix.

def naive_solve(a, b, lamda):
    return la.solve(np.dot(a.T, a) + lamda * np.identity(a.shape[1]),
                    np.dot(a.T, b))

def pos_solve(a, b, lamda):
    return la.solve(np.dot(a.T, a) + lamda * np.identity(a.shape[1]),
                    np.dot(a.T, b), assume_a='pos')

Here's a temporary analysis on my workstation *:

>>> %timeit la.lstsq(a, b)
1.84 s ± 39.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit naive_solve(a, b, 1e-25)
140 ms ± 4.15 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
>>> %timeit pos_solve(a, b, 1e-25)
135 ms ± 768 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

* I somehow didn’t have it scipy.sparse.linalg.lsmrin my car, so I could not compare with this.

, , , , assume_a='pos' . , , , A^T A , lamda . , lamda, .

:

>>> xhat_lstsq = la.lstsq(a, b)[0]
>>> la.norm(np.dot(a, xhat_lstsq) - b)
1.4628232073579952e-13
>>> xhat_naive = naive_solve(a, b, 1e-25)
>>> la.norm(np.dot(a, xhat_naive) - b)
7.474566255470176e-13
>>> xhat_pos = pos_solve(a, b, 1e-25)
>>> la.norm(np.dot(a, xhat_pos) - b)
7.476075564322223e-13

PS: a a a b :

s = np.logspace(1, -20, 500)
u = np.random.randn(100000, 500)
u /= la.norm(u, axis=0)[np.newaxis, :]
a = np.dot(u, np.diag(s))
x = np.random.randn(500)
b = np.dot(a, x)

My a , .

, . , , . 100 000 A , 500, , , (- ), . SVD , . : - . , A r, r , , r << n.

"" "" . , , . - . "", x - - , , x , .. , x , , , , - b. , .