Coverage for src/cvxcla/_lasso.py: 100%

67 statements  

« prev     ^ index     » next       coverage.py v7.17.3, created at 2026-11-17 13:36 +0000

1"""Per-segment numeric kernels for the LASSO regularisation path. 

2 

3The LASSO homotopy is driven by the same generic ``cvxcla.pathtracer.trace`` loop 

4as the Critical Line Algorithm; the two problem-specific numeric kernels live here 

5as pure functions, mirroring the CLA's ``cvxcla._kkt`` (the segment solve) and 

6``cvxcla._events`` (the critical-lambda scan). :func:`solve_segment` solves the 

7affine path valid on one segment; :func:`scan_events` stacks every candidate 

8critical lambda into the ``(n + p, 4)`` matrix the tracer scans. 

9 

10Both are pure: they take arrays (and the ``QuadraticForm`` operator) in and return 

11arrays, so ``cvxcla.lasso.Lasso`` reduces to the thin ``ParametricProblem`` glue 

12that wires them into the tracer. The two ``NamedTuple`` carriers passed between the 

13tracer and these kernels -- :class:`LassoState` (the vertex) and 

14:class:`LassoSegment` (the affine piece) -- are defined here alongside the kernels 

15that produce and consume them. 

16""" 

17 

18from __future__ import annotations 

19 

20from typing import NamedTuple 

21 

22import numpy as np 

23from numpy.typing import NDArray 

24 

25from .operators import QuadraticForm, bordered_solve 

26 

27 

28class LassoState(NamedTuple): 

29 """The support, sign pattern, active inequality rows, and current penalty. 

30 

31 ``lam`` is the penalty at the segment's upper end. Right after a coefficient 

32 enters it sits at zero, so its leave event lies at the current ``lam``; the 

33 event scan must not re-fire it, or the walk would cycle between entering and 

34 leaving the same coordinate. It tells that echo from a second event due at the 

35 same ``lam`` by direction (see :func:`scan_events`). 

36 """ 

37 

38 active: NDArray[np.bool_] 

39 signs: NDArray[np.float64] 

40 rows_active: NDArray[np.bool_] 

41 lam: float 

42 

43 

44class LassoSegment(NamedTuple): 

45 """The affine path ``beta(lam) = alpha - lam * beta_slope`` and its multipliers. 

46 

47 ``eta_alpha``/``eta_slope`` give the active-row multiplier path 

48 ``eta(lam) = eta_alpha + lam * eta_slope`` (length ``p``, nonzero only on active 

49 rows); ``p``/``q`` give the generalised correlation ``p + lam * q``. 

50 """ 

51 

52 alpha: NDArray[np.float64] 

53 beta_slope: NDArray[np.float64] 

54 p: NDArray[np.float64] 

55 q: NDArray[np.float64] 

56 eta_alpha: NDArray[np.float64] 

57 eta_slope: NDArray[np.float64] 

58 

59 

60def solve_segment( 

61 quad: QuadraticForm, 

62 xty: NDArray[np.float64], 

63 g_matrix: NDArray[np.float64], 

64 h_vector: NDArray[np.float64], 

65 state: LassoState, 

66) -> LassoSegment: 

67 """Solve the affine segment for the current support, signs, and active rows. 

68 

69 With no active rows this is the plain LASSO solve against the Gram 

70 submatrix. With active rows it is the bordered Schur solve of the CLA: the 

71 active rows ``G_S`` enter the reduced KKT system as extra equality rows. 

72 

73 Args: 

74 quad: The quadratic form ``H`` (``X^T X``) as a :class:`QuadraticForm`. 

75 xty: The linear term ``X^T y`` of shape ``(n,)``. 

76 g_matrix: Inequality matrix ``G`` of ``G beta <= h`` (``(p, n)``). 

77 h_vector: Inequality right-hand side ``h`` (length ``p``). 

78 state: The current support, signs, and active-row masks. 

79 

80 Returns: 

81 The :class:`LassoSegment` affine path and its multipliers. 

82 """ 

83 n = xty.shape[0] 

84 active, signs, rows_active = state.active, state.signs, state.rows_active 

85 alpha = np.zeros(n) 

86 beta_slope = np.zeros(n) 

87 eta_alpha = np.zeros(g_matrix.shape[0]) 

88 eta_slope = np.zeros(g_matrix.shape[0]) 

89 

90 xty_s = xty[active] 

91 signs_s = signs[active] 

92 if not np.any(active): 

93 # Empty support (e.g. the non-negative path when no correlation is 

94 # positive): beta = 0, correlation = X^T y, and there is nothing to solve. 

95 return LassoSegment(alpha, beta_slope, xty.copy(), np.zeros(n), eta_alpha, eta_slope) 

96 

97 # The active rows G_RS act as equality rows in the reduced KKT system, exactly 

98 # the CLA's bordered Schur solve (operators.bordered_solve). With no active rows 

99 # (|R| = 0) this reduces to the plain LASSO solve beta_S(lam) = H_SS^{-1}(xty_S - 

100 # lam s_S). The slope's constraint right-hand side is zero, and the slope 

101 # multiplier nu carries the opposite sign convention to eta(lam) (beta = alpha - 

102 # lam beta_slope here, vs w = r_alpha + lam r_beta in the CLA), hence the flip. 

103 g_rs = g_matrix[np.ix_(rows_active, active)] # |R| x |S| 

104 h_r = h_vector[rows_active] 

105 x_const, x_slope, eta_a, nu_slope = bordered_solve(quad, active, g_rs, xty_s, signs_s, h_r, np.zeros(g_rs.shape[0])) 

106 alpha[active] = x_const 

107 beta_slope[active] = x_slope 

108 eta_alpha[rows_active] = eta_a 

109 eta_slope[rows_active] = -nu_slope 

110 

111 # Generalised correlation c(lam) = xty - H beta(lam) - G_R^T eta(lam) = p + lam q. 

112 g_r = g_matrix[rows_active] 

113 eta_a_r = eta_alpha[rows_active] 

114 eta_s_r = eta_slope[rows_active] 

115 p = xty - quad.matvec(alpha) - g_r.T @ eta_a_r 

116 q = quad.matvec(beta_slope) - g_r.T @ eta_s_r 

117 return LassoSegment(alpha, beta_slope, p, q, eta_alpha, eta_slope) 

118 

119 

120def scan_events( 

121 n: int, 

122 g_matrix: NDArray[np.float64], 

123 h_vector: NDArray[np.float64], 

124 tol: float, 

125 nonneg: bool, 

126 state: LassoState, 

127 segment: LassoSegment, 

128) -> NDArray[np.float64]: 

129 """Return the ``(n + p, 4)`` matrix of candidate critical lambdas. 

130 

131 Rows ``0..n-1`` are coordinate events (col 0 leave, col 1 enter ``+``, col 2 

132 enter ``-``); rows ``n..n+p-1`` are inequality-row events (col 0 activate, col 

133 1 release). Entries are ``-inf`` where the event cannot occur. 

134 

135 Every event is kept only in the direction in which it can happen: a coefficient 

136 leaves while shrinking through zero against its sign, and a coordinate enters 

137 while its correlation crosses ``+/- lam`` outwards. An event that does not move 

138 that way is the echo of the one just taken (a coefficient that has just entered 

139 sits at zero but grows), and is dropped. Events within ``tol`` of the current 

140 ``lam`` that do move that way are due now and are kept at ``lam``: two events 

141 can coincide, as when nearly collinear columns swap, and the one taken second 

142 would otherwise be lost and the path continue with a wrong sign. 

143 

144 Args: 

145 n: The problem dimension (number of features). 

146 g_matrix: Inequality matrix ``G`` of ``G beta <= h`` (``(p, n)``). 

147 h_vector: Inequality right-hand side ``h`` (length ``p``). 

148 tol: Tolerance for event selection and the validity window. 

149 nonneg: When ``True`` the enter-negative events are disabled (``beta >= 0``). 

150 state: The current support, signs, and active-row masks. 

151 segment: The affine path and multipliers from :func:`solve_segment`. 

152 

153 Returns: 

154 The ``(n + p, 4)`` matrix of critical lambdas. 

155 """ 

156 rows = g_matrix.shape[0] 

157 active = state.active 

158 inactive = ~active 

159 alpha, beta_slope, p, q, eta_alpha, eta_slope = segment 

160 rows_active = state.rows_active 

161 

162 l_mat = np.full((n + rows, 4), -np.inf) 

163 

164 # leave: alpha_j - lam beta_slope_j = 0. As lam decreases beta_j moves by 

165 # beta_slope_j, so it shrinks through zero only when that is against its sign. 

166 leaves = active & (np.abs(beta_slope) > tol) & (state.signs * beta_slope < 0) # pragma: no mutate 

167 l_mat[:n][leaves, 0] = alpha[leaves] / beta_slope[leaves] 

168 

169 # enter (+): p_j + lam q_j = +lam -> lam = p_j / (1 - q_j). Below it the 

170 # correlation exceeds +lam only when 1 - q_j > 0. 

171 denom_pos = 1.0 - q 

172 enters_pos = inactive & (denom_pos > tol) # pragma: no mutate 

173 l_mat[:n][enters_pos, 1] = p[enters_pos] / denom_pos[enters_pos] 

174 

175 # enter (-): p_j + lam q_j = -lam -> lam = -p_j / (1 + q_j), crossed outwards 

176 # only when 1 + q_j > 0. Disabled under the non-negative restriction beta >= 0, 

177 # where only positive entries are allowed. 

178 if not nonneg: 

179 denom_neg = 1.0 + q 

180 enters_neg = inactive & (denom_neg > tol) # pragma: no mutate 

181 l_mat[:n][enters_neg, 2] = -p[enters_neg] / denom_neg[enters_neg] 

182 

183 if rows: 

184 slope_row = g_matrix @ beta_slope # d/d(-lam) of the row value 

185 level_row = g_matrix @ alpha - h_vector # G_r alpha - h_r 

186 # activate: the row value G_r beta(lam) = level + h_r - lam slope rises to 

187 # the cap h_r as lam decreases when its slope d(value)/d(-lam) = slope_row 

188 # is positive; the crossing is lam = (G_r alpha - h_r) / (G_r beta_slope). 

189 inactive_rows = ~rows_active & (slope_row > tol) # pragma: no mutate 

190 l_mat[n:][inactive_rows, 0] = level_row[inactive_rows] / slope_row[inactive_rows] 

191 # release: eta_r(lam) = eta_alpha + lam eta_slope -> 0 from eta > 0, i.e. eta_slope > 0. 

192 releasing = rows_active & (eta_slope > tol) # pragma: no mutate 

193 l_mat[n:][releasing, 1] = -eta_alpha[releasing] / eta_slope[releasing] 

194 

195 # Keep events at a positive penalty no larger than the current one; those that 

196 # round to just above it are due now. 

197 l_mat[(l_mat <= tol) | (l_mat > state.lam + tol)] = -np.inf 

198 np.minimum(l_mat, state.lam, out=l_mat) 

199 return l_mat