Coverage for src/cvx/linalg/decomposition/svd.py: 100%

1"""Raw singular value decomposition utilities.""" 

2 

3from __future__ import annotations 

4 

5import numpy as np 

6 

7from ..core.exceptions import InvalidComponentsError 

8from ..core.types import Matrix, Vector 

9 

10 

11def svd(matrix: Matrix) -> tuple[Matrix, Matrix, Matrix]: 

12 """Compute the compact singular value decomposition of a matrix. 

13 

14 This is a thin wrapper around ``numpy.linalg.svd`` with 

15 ``full_matrices=False``. 

16 

17 Args: 

18 matrix: Input matrix of shape ``(m, n)``. 

19 

20 Returns: 

21 Tuple ``(u, s, vt)`` such that ``matrix == u @ np.diag(s) @ vt``. 

22 """ 

23 return np.linalg.svd(matrix, full_matrices=False) 

24 

25 

26def svd_k(matrix: Matrix, k: int) -> tuple[Matrix, Vector, Matrix]: 

27 """Compute the truncated rank-``k`` singular value decomposition. 

28 

29 Returns the ``k`` leading singular triplets — the best rank-``k`` 

30 approximation of *matrix* in both the spectral and Frobenius norms 

31 (Eckart-Young). This is an *exact* truncation: the full compact SVD is 

32 computed and sliced, so the result is deterministic and matches 

33 :func:`numpy.linalg.svd` on the leading components. Like :func:`svd`, it is 

34 a raw decomposition and is **not** NaN-aware; clean non-finite entries 

35 first. 

36 

37 Args: 

38 matrix: Input matrix of shape ``(m, n)``. 

39 k: Number of leading singular triplets to keep. Must be between 1 and 

40 ``min(m, n)``. 

41 

42 Returns: 

43 Tuple ``(u, s, vt)`` with shapes ``(m, k)``, ``(k,)`` and ``(k, n)``, 

44 such that ``u @ np.diag(s) @ vt`` is the best rank-``k`` approximation 

45 of *matrix*. Singular values are in descending order. 

46 

47 Raises: 

48 InvalidComponentsError: If *k* is smaller than 1 or larger than 

49 ``min(m, n)``. 

50 

51 Example: 

52 >>> import numpy as np 

53 >>> from cvx.linalg import svd_k 

54 >>> matrix = np.diag([3.0, 2.0, 1.0]) @ np.ones((3, 4)) 

55 >>> u, s, vt = svd_k(matrix, k=1) 

56 >>> u.shape, s.shape, vt.shape 

57 ((3, 1), (1,), (1, 4)) 

58 

59 The leading triplets agree with the full SVD: 

60 

61 >>> u_full, s_full, vt_full = np.linalg.svd(matrix, full_matrices=False) 

62 >>> bool(np.allclose(s, s_full[:1])) 

63 True 

64 

65 ``svd_k(matrix, min(m, n))`` reconstructs the matrix exactly: 

66 

67 >>> u, s, vt = svd_k(matrix, k=3) 

68 >>> bool(np.allclose(u @ np.diag(s) @ vt, matrix)) 

69 True 

70 """ 

71 max_components = min(matrix.shape) 

72 if not 1 <= k <= max_components: 

73 raise InvalidComponentsError(k, max_components) 

74 

75 u, s, vt = np.linalg.svd(matrix, full_matrices=False) 

76 return u[:, :k], s[:k], vt[:k, :]