File size: 7,660 Bytes
7885a28 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 |
from itertools import product, permutations
import numpy as np
import pytest
from numpy.testing import assert_array_less, assert_allclose
from pytest import raises as assert_raises
from scipy.linalg import inv, eigh, norm, svd
from scipy.linalg import orthogonal_procrustes
from scipy.sparse._sputils import matrix
def test_orthogonal_procrustes_ndim_too_large():
rng = np.random.RandomState(1234)
A = rng.randn(3, 4, 5)
B = rng.randn(3, 4, 5)
assert_raises(ValueError, orthogonal_procrustes, A, B)
def test_orthogonal_procrustes_ndim_too_small():
rng = np.random.RandomState(1234)
A = rng.randn(3)
B = rng.randn(3)
assert_raises(ValueError, orthogonal_procrustes, A, B)
def test_orthogonal_procrustes_shape_mismatch():
rng = np.random.RandomState(1234)
shapes = ((3, 3), (3, 4), (4, 3), (4, 4))
for a, b in permutations(shapes, 2):
A = rng.randn(*a)
B = rng.randn(*b)
assert_raises(ValueError, orthogonal_procrustes, A, B)
def test_orthogonal_procrustes_checkfinite_exception():
rng = np.random.RandomState(1234)
m, n = 2, 3
A_good = rng.randn(m, n)
B_good = rng.randn(m, n)
for bad_value in np.inf, -np.inf, np.nan:
A_bad = A_good.copy()
A_bad[1, 2] = bad_value
B_bad = B_good.copy()
B_bad[1, 2] = bad_value
for A, B in ((A_good, B_bad), (A_bad, B_good), (A_bad, B_bad)):
assert_raises(ValueError, orthogonal_procrustes, A, B)
def test_orthogonal_procrustes_scale_invariance():
rng = np.random.RandomState(1234)
m, n = 4, 3
for i in range(3):
A_orig = rng.randn(m, n)
B_orig = rng.randn(m, n)
R_orig, s = orthogonal_procrustes(A_orig, B_orig)
for A_scale in np.square(rng.randn(3)):
for B_scale in np.square(rng.randn(3)):
R, s = orthogonal_procrustes(A_orig * A_scale, B_orig * B_scale)
assert_allclose(R, R_orig)
def test_orthogonal_procrustes_array_conversion():
rng = np.random.RandomState(1234)
for m, n in ((6, 4), (4, 4), (4, 6)):
A_arr = rng.randn(m, n)
B_arr = rng.randn(m, n)
As = (A_arr, A_arr.tolist(), matrix(A_arr))
Bs = (B_arr, B_arr.tolist(), matrix(B_arr))
R_arr, s = orthogonal_procrustes(A_arr, B_arr)
AR_arr = A_arr.dot(R_arr)
for A, B in product(As, Bs):
R, s = orthogonal_procrustes(A, B)
AR = A_arr.dot(R)
assert_allclose(AR, AR_arr)
def test_orthogonal_procrustes():
rng = np.random.RandomState(1234)
for m, n in ((6, 4), (4, 4), (4, 6)):
# Sample a random target matrix.
B = rng.randn(m, n)
# Sample a random orthogonal matrix
# by computing eigh of a sampled symmetric matrix.
X = rng.randn(n, n)
w, V = eigh(X.T + X)
assert_allclose(inv(V), V.T)
# Compute a matrix with a known orthogonal transformation that gives B.
A = np.dot(B, V.T)
# Check that an orthogonal transformation from A to B can be recovered.
R, s = orthogonal_procrustes(A, B)
assert_allclose(inv(R), R.T)
assert_allclose(A.dot(R), B)
# Create a perturbed input matrix.
A_perturbed = A + 1e-2 * rng.randn(m, n)
# Check that the orthogonal procrustes function can find an orthogonal
# transformation that is better than the orthogonal transformation
# computed from the original input matrix.
R_prime, s = orthogonal_procrustes(A_perturbed, B)
assert_allclose(inv(R_prime), R_prime.T)
# Compute the naive and optimal transformations of the perturbed input.
naive_approx = A_perturbed.dot(R)
optim_approx = A_perturbed.dot(R_prime)
# Compute the Frobenius norm errors of the matrix approximations.
naive_approx_error = norm(naive_approx - B, ord='fro')
optim_approx_error = norm(optim_approx - B, ord='fro')
# Check that the orthogonal Procrustes approximation is better.
assert_array_less(optim_approx_error, naive_approx_error)
def _centered(A):
mu = A.mean(axis=0)
return A - mu, mu
def test_orthogonal_procrustes_exact_example():
# Check a small application.
# It uses translation, scaling, reflection, and rotation.
#
# |
# a b |
# |
# d c | w
# |
# --------+--- x ----- z ---
# |
# | y
# |
#
A_orig = np.array([[-3, 3], [-2, 3], [-2, 2], [-3, 2]], dtype=float)
B_orig = np.array([[3, 2], [1, 0], [3, -2], [5, 0]], dtype=float)
A, A_mu = _centered(A_orig)
B, B_mu = _centered(B_orig)
R, s = orthogonal_procrustes(A, B)
scale = s / np.square(norm(A))
B_approx = scale * np.dot(A, R) + B_mu
assert_allclose(B_approx, B_orig, atol=1e-8)
def test_orthogonal_procrustes_stretched_example():
# Try again with a target with a stretched y axis.
A_orig = np.array([[-3, 3], [-2, 3], [-2, 2], [-3, 2]], dtype=float)
B_orig = np.array([[3, 40], [1, 0], [3, -40], [5, 0]], dtype=float)
A, A_mu = _centered(A_orig)
B, B_mu = _centered(B_orig)
R, s = orthogonal_procrustes(A, B)
scale = s / np.square(norm(A))
B_approx = scale * np.dot(A, R) + B_mu
expected = np.array([[3, 21], [-18, 0], [3, -21], [24, 0]], dtype=float)
assert_allclose(B_approx, expected, atol=1e-8)
# Check disparity symmetry.
expected_disparity = 0.4501246882793018
AB_disparity = np.square(norm(B_approx - B_orig) / norm(B))
assert_allclose(AB_disparity, expected_disparity)
R, s = orthogonal_procrustes(B, A)
scale = s / np.square(norm(B))
A_approx = scale * np.dot(B, R) + A_mu
BA_disparity = np.square(norm(A_approx - A_orig) / norm(A))
assert_allclose(BA_disparity, expected_disparity)
def test_orthogonal_procrustes_skbio_example():
# This transformation is also exact.
# It uses translation, scaling, and reflection.
#
# |
# | a
# | b
# | c d
# --+---------
# |
# | w
# |
# | x
# |
# | z y
# |
#
A_orig = np.array([[4, -2], [4, -4], [4, -6], [2, -6]], dtype=float)
B_orig = np.array([[1, 3], [1, 2], [1, 1], [2, 1]], dtype=float)
B_standardized = np.array([
[-0.13363062, 0.6681531],
[-0.13363062, 0.13363062],
[-0.13363062, -0.40089186],
[0.40089186, -0.40089186]])
A, A_mu = _centered(A_orig)
B, B_mu = _centered(B_orig)
R, s = orthogonal_procrustes(A, B)
scale = s / np.square(norm(A))
B_approx = scale * np.dot(A, R) + B_mu
assert_allclose(B_approx, B_orig)
assert_allclose(B / norm(B), B_standardized)
def test_empty():
a = np.empty((0, 0))
r, s = orthogonal_procrustes(a, a)
assert_allclose(r, np.empty((0, 0)))
a = np.empty((0, 3))
r, s = orthogonal_procrustes(a, a)
assert_allclose(r, np.identity(3))
@pytest.mark.parametrize('shape', [(4, 5), (5, 5), (5, 4)])
def test_unitary(shape):
# gh-12071 added support for unitary matrices; check that it
# works as intended.
m, n = shape
rng = np.random.default_rng(589234981235)
A = rng.random(shape) + rng.random(shape) * 1j
Q = rng.random((n, n)) + rng.random((n, n)) * 1j
Q, _ = np.linalg.qr(Q)
B = A @ Q
R, scale = orthogonal_procrustes(A, B)
assert_allclose(R @ R.conj().T, np.eye(n), atol=1e-14)
assert_allclose(A @ Q, B)
if shape != (4, 5): # solution is unique
assert_allclose(R, Q)
_, s, _ = svd(A.conj().T @ B)
assert_allclose(scale, np.sum(s))
|