Skip to main content

solow_regression/
recursive.rs

1//! Recursive least squares (RLS).
2//!
3//! The regression coefficients are updated observation-by-observation as data
4//! arrives. Equivalently, this is the exact-diffuse Kalman filter applied to the
5//! state-space form of the linear model (state = the coefficient vector, a random
6//! walk with zero innovation variance; observation = `yₜ = xₜᵀ β + εₜ`). That
7//! formulation reproduces the canonical reference's quantities exactly:
8//!
9//! * the *filtered recursive coefficients* (one vector per observation),
10//! * the concentrated Gaussian *log-likelihood* (`llf`, `llf_obs`) — the first
11//!   `k` (= number of regressors) observations form the diffuse phase and use the
12//!   diffuse forecast-variance term `−½(ln 2π + ln F∞)`,
13//! * the standardized *recursive residuals*, and the
14//! * *CUSUM* and *CUSUM-of-squares* structural-stability statistics.
15
16use ndarray::{Array1, Array2};
17use solow_core::error::{Error, Result};
18use std::f64::consts::PI;
19
20/// A recursive-least-squares model awaiting `fit`.
21#[derive(Clone, Debug)]
22pub struct RecursiveLS {
23    endog: Array1<f64>,
24    exog: Array2<f64>,
25}
26
27impl RecursiveLS {
28    /// Build a recursive-least-squares model from response and design.
29    pub fn new(endog: Array1<f64>, exog: Array2<f64>) -> Result<Self> {
30        if endog.len() != exog.nrows() {
31            return Err(Error::Shape("endog length != exog rows".into()));
32        }
33        if exog.nrows() == 0 {
34            return Err(Error::Value("empty design matrix".into()));
35        }
36        Ok(RecursiveLS { endog, exog })
37    }
38
39    /// Run the recursion and assemble all results.
40    pub fn fit(&self) -> Result<RecursiveLSResults> {
41        let (n, k) = self.exog.dim();
42        if n < k {
43            return Err(Error::Value(
44                "need at least as many observations as regressors".into(),
45            ));
46        }
47
48        // -- Pass 1: exact-diffuse Kalman filter --------------------------------
49        // State a (k), diffuse covariance P∞ = I, stationary covariance P* = 0,
50        // observation variance H = 1 (the scale is concentrated out afterwards).
51        // During the diffuse phase F∞ = xₜᵀ P∞ xₜ > 0; once P∞ collapses to 0 the
52        // filter switches to the ordinary recursion.
53        let mut a = Array1::<f64>::zeros(k);
54        let mut p_inf = Array2::<f64>::eye(k);
55        let mut p_star = Array2::<f64>::zeros((k, k));
56        let h = 1.0;
57
58        // Standardized recursive residuals vₜ / √Fₜ (only defined post-diffuse;
59        // zero during the diffuse phase, matching the reference).
60        let mut resid_recursive = Array1::<f64>::zeros(n);
61        // Per-observation forecast variance (for the concentrated llf below).
62        let mut diffuse = vec![false; n];
63        let mut f_used = Array1::<f64>::zeros(n); // F∞ in diffuse phase, F* after
64        let mut v_used = Array1::<f64>::zeros(n); // forecast error vₜ
65                                                  // Recursive coefficient path: filtered state after each update.
66        let mut coefs = Array2::<f64>::zeros((n, k));
67        let mut nobs_diffuse = 0usize;
68
69        for t in 0..n {
70            let xt = self.exog.row(t).to_owned();
71            let v = self.endog[t] - xt.dot(&a);
72            let m_inf = p_inf.dot(&xt);
73            let m_star = p_star.dot(&xt);
74            let f_inf = xt.dot(&m_inf);
75            let f_star = xt.dot(&m_star) + h;
76            v_used[t] = v;
77
78            if f_inf > 1e-12 {
79                // Diffuse update (Durbin–Koopman exact-diffuse recursion).
80                diffuse[t] = true;
81                nobs_diffuse += 1;
82                f_used[t] = f_inf;
83                let k0 = &m_inf / f_inf;
84                a = &a + &(&k0 * v);
85                // P* = P* + M∞ M∞ᵀ F*/F∞² − (M* M∞ᵀ + M∞ M*ᵀ)/F∞
86                let outer_inf = outer(&m_inf, &m_inf);
87                let cross = &outer(&m_star, &m_inf) + &outer(&m_inf, &m_star);
88                p_star = &p_star + &(&outer_inf * (f_star / (f_inf * f_inf))) - &(&cross / f_inf);
89                // P∞ = P∞ − M∞ M∞ᵀ / F∞
90                p_inf = &p_inf - &(&outer_inf / f_inf);
91                // recursive residual undefined during diffuse phase
92                resid_recursive[t] = 0.0;
93            } else {
94                // Ordinary Kalman/RLS update.
95                f_used[t] = f_star;
96                let kk = &m_star / f_star;
97                a = &a + &(&kk * v);
98                p_star = &p_star - &(&outer(&m_star, &m_star) / f_star);
99                resid_recursive[t] = v / f_star.sqrt();
100            }
101            for j in 0..k {
102                coefs[[t, j]] = a[j];
103            }
104        }
105
106        let params = a.clone();
107
108        // -- Concentrated scale from post-diffuse standardized residuals --------
109        let d = nobs_diffuse;
110        let n_eff = (n - d) as f64;
111        let mut ssr = 0.0;
112        for t in d..n {
113            ssr += resid_recursive[t] * resid_recursive[t];
114        }
115        let scale = ssr / n_eff;
116
117        // -- Per-observation concentrated log-likelihood ------------------------
118        // Diffuse obs: −½(ln 2π + ln F∞).
119        // Post-diffuse obs: −½(ln 2π + ln(scale·F*) + vₜ²/(scale·F*)).
120        let mut llf_obs = Array1::<f64>::zeros(n);
121        for t in 0..n {
122            if diffuse[t] {
123                llf_obs[t] = -0.5 * ((2.0 * PI).ln() + f_used[t].ln());
124            } else {
125                let sf = scale * f_used[t];
126                llf_obs[t] = -0.5 * ((2.0 * PI).ln() + sf.ln() + v_used[t] * v_used[t] / sf);
127            }
128        }
129        let llf = llf_obs.sum();
130
131        // -- CUSUM / CUSUM-of-squares over post-diffuse recursive residuals -----
132        let post: Vec<f64> = (d..n).map(|t| resid_recursive[t]).collect();
133        let m = post.len();
134        // Sample std with ddof = 1 (matching np.std(..., ddof=1)).
135        let mean: f64 = post.iter().sum::<f64>() / m as f64;
136        let var: f64 = post.iter().map(|x| (x - mean).powi(2)).sum::<f64>() / (m as f64 - 1.0);
137        let sd = var.sqrt();
138        let mut cusum = Array1::<f64>::zeros(m);
139        let mut acc = 0.0;
140        for (i, &w) in post.iter().enumerate() {
141            acc += w;
142            cusum[i] = acc / sd;
143        }
144        let mut cusum_squares = Array1::<f64>::zeros(m);
145        let mut acc2 = 0.0;
146        let denom: f64 = post.iter().map(|w| w * w).sum();
147        for (i, &w) in post.iter().enumerate() {
148            acc2 += w * w;
149            cusum_squares[i] = acc2 / denom;
150        }
151
152        Ok(RecursiveLSResults {
153            params,
154            recursive_coefficients: coefs,
155            resid_recursive,
156            llf,
157            llf_obs,
158            scale,
159            nobs_diffuse: d,
160            nobs: n as f64,
161            k_exog: k,
162            cusum,
163            cusum_squares,
164        })
165    }
166}
167
168/// The fitted result of a [`RecursiveLS`].
169#[derive(Clone, Debug)]
170pub struct RecursiveLSResults {
171    /// Final (full-sample) coefficient estimates.
172    pub params: Array1<f64>,
173    /// Filtered recursive coefficients — one row per observation.
174    pub recursive_coefficients: Array2<f64>,
175    /// Standardized recursive residuals (zero during the diffuse phase).
176    pub resid_recursive: Array1<f64>,
177    /// Concentrated Gaussian log-likelihood.
178    pub llf: f64,
179    /// Per-observation log-likelihood contributions (sums to `llf`).
180    pub llf_obs: Array1<f64>,
181    /// Concentrated scale (residual variance) estimate.
182    pub scale: f64,
183    /// Number of diffuse-phase observations (equals the number of regressors).
184    pub nobs_diffuse: usize,
185    /// Number of observations.
186    pub nobs: f64,
187    /// Number of regressors.
188    pub k_exog: usize,
189    /// CUSUM of standardized recursive residuals (`nobs − nobs_diffuse` long).
190    pub cusum: Array1<f64>,
191    /// CUSUM of squared standardized recursive residuals (ending at 1).
192    pub cusum_squares: Array1<f64>,
193}
194
195/// Outer product `a bᵀ`.
196fn outer(a: &Array1<f64>, b: &Array1<f64>) -> Array2<f64> {
197    let n = a.len();
198    let m = b.len();
199    let mut out = Array2::<f64>::zeros((n, m));
200    for i in 0..n {
201        for j in 0..m {
202            out[[i, j]] = a[i] * b[j];
203        }
204    }
205    out
206}
207
208#[cfg(test)]
209mod tests {
210    use super::*;
211    use ndarray::array;
212
213    #[test]
214    fn final_coefficients_equal_full_sample_ols() {
215        // RLS final state must equal the OLS fit on all observations.
216        let x = array![
217            [1.0, 0.0],
218            [1.0, 1.0],
219            [1.0, 2.0],
220            [1.0, 4.0],
221            [1.0, 5.0],
222            [1.0, 7.0]
223        ];
224        let y = array![1.1, 2.9, 5.2, 8.8, 11.1, 15.3];
225        let res = RecursiveLS::new(y.clone(), x.clone())
226            .unwrap()
227            .fit()
228            .unwrap();
229
230        // Closed-form OLS via normal equations.
231        let xtx = x.t().dot(&x);
232        let xtxi = solow_linalg::inv(&xtx).unwrap();
233        let ols = xtxi.dot(&x.t().dot(&y));
234        for j in 0..2 {
235            assert!((res.params[j] - ols[j]).abs() < 1e-9, "coef {j}");
236        }
237        assert_eq!(res.nobs_diffuse, 2);
238    }
239
240    #[test]
241    fn diffuse_phase_residuals_are_zero_and_cusum_squares_ends_at_one() {
242        let x = array![
243            [1.0, 0.5],
244            [1.0, -0.3],
245            [1.0, 1.2],
246            [1.0, 0.8],
247            [1.0, -1.1],
248            [1.0, 0.2]
249        ];
250        let y = array![0.9, 0.1, 2.0, 1.7, -1.3, 0.6];
251        let res = RecursiveLS::new(y, x).unwrap().fit().unwrap();
252        // First k residuals are zero (diffuse).
253        for t in 0..res.nobs_diffuse {
254            assert_eq!(res.resid_recursive[t], 0.0);
255        }
256        // CUSUM-of-squares is a fraction ending exactly at 1.
257        let last = res.cusum_squares[res.cusum_squares.len() - 1];
258        assert!((last - 1.0).abs() < 1e-12);
259        // llf_obs sums to llf.
260        assert!((res.llf_obs.sum() - res.llf).abs() < 1e-12);
261    }
262}