Home:ALL Converter>How to solve overdetermined linear system X * A = B?

How to solve overdetermined linear system X * A = B?

Ask Time:2020-08-27T05:55:19         Author:mrgloom

Json Formatter

How to solve overdetermined linear system X * A = B, A, B is given and I need to find X?

It seems solution is straightforward for square matrices(https://stackoverflow.com/a/18848074/1179925):

X * A = B
M * A * Inv(A) = B * Inv(A)
M = B * Inv(A)

But how to deal with non square matrices?

Example code:

def to_homogeneous(_pts):
    n = _pts.shape[0]
    _pts = _pts.transpose()
    pts = np.ones((3,n), np.float32)
    pts[:2,:] = _pts
    return pts

def get_random_affine_matrix():
    src_tri = np.random.rand(3,2) * np.random.randint(1,10)
    src_tri = src_tri.astype(np.float32)
    src_tri = to_homogeneous(src_tri)
    
    dst_tri = np.random.rand(3,2) * np.random.randint(1,10)
    dst_tri = dst_tri.astype(np.float32)
    dst_tri = to_homogeneous(dst_tri)
    
    m = dst_tri @ np.linalg.inv(src_tri)
    
    print('-'*60)
    print('src_tri.shape', src_tri.shape)
    print('src_tri:')
    print(src_tri)

    print('-'*60)
    print('dst_tri.shape', dst_tri.shape)
    print('dst_tri:')
    print(dst_tri)

    print('-'*60)
    print('m.shape', m.shape)
    print('m:')
    print(np.round(m, 5))

    return m

m = get_random_affine_matrix()

src_pts = np.random.rand(4,2) * np.random.randint(1,10)
src_pts = src_pts.astype(np.float32)
src_pts = to_homogeneous(src_pts)

dst_pts = m @ src_pts

print('-'*60)
print('src_pts.shape', src_pts.shape)
print('src_pts:')
print(src_pts)

print('-'*60)
print('dst_pts.shape', dst_pts.shape)
print('dst_pts:')
print(dst_pts)

m = dst_pts @ np.linalg.inv(src_pts) # Gives LinAlgError: Last 2 dimensions of the array must be square

Output:

------------------------------------------------------------
src_tri.shape (3, 3)
src_tri:
[[2.7440674 3.0138168 2.118274 ]
 [3.5759468 2.724416  3.2294705]
 [1.        1.        1.       ]]
------------------------------------------------------------
dst_tri.shape (3, 3)
dst_tri:
[[0.5950692  0.5453126  1.6243374 ]
 [0.11342596 0.95533025 0.9599543 ]
 [1.         1.         1.        ]]
------------------------------------------------------------
m.shape (3, 3)
m:
[[-1.42684 -0.39356  5.91778]
 [-0.68516 -1.20574  6.30521]
 [ 0.       0.       1.     ]]
------------------------------------------------------------
src_pts.shape (3, 4)
src_pts:
[[8.33037    0.7841637  7.4935784  7.830109  ]
 [0.63932455 0.18196557 7.003411   8.807565  ]
 [1.         1.         1.         1.        ]]
------------------------------------------------------------
dst_pts.shape (3, 4)
dst_pts:
[[-6.2199397   4.7272906  -7.5306525  -8.7208805 ]
 [-0.17327118  5.5485325  -7.2733746  -9.679293  ]
 [ 1.0000011   1.0000001   1.0000015   1.0000017 ]]

LinAlgError: Last 2 dimensions of the array must be square

Author:mrgloom,eproduced under the CC 4.0 BY-SA copyright license with a link to the original source and this disclaimer.
Link to original article:https://stackoverflow.com/questions/63606270/how-to-solve-overdetermined-linear-system-x-a-b
Miguel :

I think the best solution would be using numpy's lstsq function:\nrewriting your system like this\n#X*A = B <=> A.T*X.T = B.T\n\nlets us use\nXt = np.linalg.lstsq(A.T, B.T)\nX = Xt.T\n\nThis is a better solution both in terms of speed and accuracy to using inverses and pseudo-inverses, and unless you explicitly need these I would strongly recommend that you don't use them",
2020-08-27T05:41:32
yy