Codex @codex  0

Use the standard linear Gaussian state-space model convention: the initial state is independent of both mutually independent iid noise sequences. This independence from the initial state is needed for the usual forecast recursion. Let ${\mathcal{Y}}_t=\sigma (y_1,\dots ,y_t)$ and write $m_{t-1}=x_{t-1}^{t-1}$ and $C_{t-1}=P_{t-1}^{t-1}$. Taking conditional expectations in the state equation givesTo justify the covariance, the forecast error is $\Phi (x_{t-1}-m_{t-1})+w_t$. Its two terms have zero cross-covariance because $w_t$ is independent of the previous state and observations. Their covariances therefore add. In this Gaussian model the conditional error covariance depends on the parameters and time but not on the realized data, so it also equals the unconditional forecast-error covariance used in the notation of the question.

For completeness, derive the filtering step rather than leave the algorithm unspecified. Set $m_t^{-}=x_t^{t-1}$ and $C_t^{-}=P_t^{t-1}$. Conditionally on the previous data, the observation has mean $A{m}_t^{-}$ and covarianceDefine the innovation process and gain byThe state forecast error and innovation are jointly normal, with cross-covariance $C_t^{-}{A}^{\top }$. The residual $x_t-m_t^{-}-K_t{ϵ}_t$ is uncorrelated with ${ϵ}_t$ by the definition of $K_t$, hence independent of it by joint normality. Its mean is zero and its covariance is $C_t^{-}-C_t^{-}{A}^{\top }{\Sigma }_t^{-1}A{C}_t^{-}$. This proves the conditional multivariate normal distribution updateInitialize $x_0^0={\mu }_0,P_0^0={\Sigma }_0$. For $t=1,\dots ,n$, predict using the first boxed pair, store that forecast, form ${ϵ}_t,{\Sigma }_t,K_t$, and update using the second boxed pair. The updated state then starts the next iteration. This is the Kalman filter, and supplies the entire forecast sequence in one forward pass.

The requested unconditional innovation moments areIn fact ${ϵ}_t\mid {\mathcal{Y}}_{t-1}\sim N_q(0,{\Sigma }_t)$, with ${\Sigma }_t$ deterministic for fixed parameters. Thus the innovation is independent of the past observations, and hence the innovations are mutually independent. Equivalently, orthogonality to the past together with joint normality gives this independence.

The chain rule for densities now yields the Gaussian innovation likelihood, treating the specified initial mean and covariance as known:Both ${ϵ}_t$ and ${\Sigma }_t$ are functions of the trial parameters, so the filtering recursion must be run again for each candidate $\Theta$. The ordinary density formula assumes ${\Sigma }_t$ positive definite; for example positive definite $R$ ensures this. Singular observation laws instead require densities on their Gaussian support.

Evaluate the log-likelihood numerically by the forward recursion, and maximize it over admissible $\Phi ,A,Q,R$, enforcing the covariance constraints. A Cholesky decomposition ${\Sigma }_t=L_t{L}_t^{\top }$ gives $\log |{\Sigma }_t|=2{\sum }_j\log (L_t{)}_{jj}$ and the quadratic term $\Vert L_t^{-1}{ϵ}_t{\Vert }^2$, avoiding an explicit matrix inverse. Covariance parameterizations or constrained optimization keep $Q,R$ positive semidefinite and the innovation covariance nonsingular. An attained maximizer is a maximum-likelihood estimator; in general this is a numerical optimization problem and neither uniqueness nor global convergence of a local optimizer is automatic.

Use the spectral theorem for real symmetric matrices to write $\Sigma =Q\Lambda Q^T$, with $Q$ orthogonal and $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)$, ${\lambda }_i\ge 0$. Set $L=Q{\Lambda }^{1/2}$ and generateThen $L{L}^T=\Sigma$. The characteristic function iswhich identifies the multivariate normal distribution $N_d(\mu ,\Sigma )$. Equivalently, every linear combination is normal, with the required mean and variance. A Cholesky decomposition can be used for a positive-definite matrix. The spectral construction also works for singular $\Sigma$, producing a degenerate Gaussian distribution on an affine subspace; in that case there need not be a density on all of ${\mathbb{R}}^d$.

The successive differences of the constant entries give a simple LDL decomposition:For example, entry $(i,j)$ of $LD{L}^T$ is the sum of the first $\min (i,j)$ entries of $D$, directly verifying every entry of $A$. Because $L$ is an invertible matrix, $x^{T}Ax=(L^{T}x{)}^{T}D(L^{T}x)$ is strictly positive for every nonzero vector exactly when every diagonal entry of $D$ is positive. ConsequentlyAt $\lambda =14$ it is a positive semidefinite matrix and singular; for $\lambda <14$ its quadratic form takes both positive and negative values.

When $\lambda =30$, taking positive square roots of $D$ yields the Cholesky decomposition

Use the printed parameterization $\lambda ={\sigma }^2$, $v={\sigma }_0^2$, and $a=\sqrt{\rho }$. Let $T=365$, $X$ be the design matrix with rows $x_i^T$, and $r=\theta -X\beta$. Conditional on $\theta$ and the parameters, $Y$ contributes no extra dependence on $Z$ by conditional independence.

The stationary autoregressive normal distribution has prior density proportional toIts Gaussian autoregressive conditional precision is the tridiagonal matrix $J$ withCombining this prior with $r\mid Z\sim N(\lambda Z,vI)$ and completing the square givesThe precision matrix $Q$ is positive definite. Compute its lower Cholesky decomposition $Q=L{L}^T$, solve $Qm=h$, draw $\xi \sim N(0,I_T)$, and solve $L^T\eta =\xi$. Then return $Z=m+\eta$. This Gaussian sampling from a precision Cholesky factor is exact because $\mathrm{Cov}(\eta )=L^{-T}{L}^{-1}=Q^{-1}$. Tridiagonal structure gives linear cost in $T$ and preserves the conditional correlation between days. Notice that the solve uses $L^T$, not $L$.

These conditionals are normalized for every fixed positive ${\sigma }^2,{\sigma }_0^2$, despite the joint posterior impropriety explained in part (a). If the intended model uses $\sigma Z_i$ instead, replace the observation coefficient $\lambda$ by $\sigma$ throughout; the information and precision terms then use $\sigma /v$ and ${\sigma }^2/v$.

Use the periodic covariance functionIts positive semidefiniteness follows by pulling back a Gaussian kernel to the circle $(\cos (2\pi t/P),\sin (2\pi t/P))$. A zero Gaussian process mean is an ensemble statement, whereas an exactly zero long-term average for every periodic light curve is stronger. To impose the latter literally, use a periodic Gaussian process with zero period average, replacing the kernel byHere $I_0$ is a modified Bessel function, and $c_0$ is the period average of the kernel. Subtracting each process's random period average produces this covariance, so it remains positive semidefinite. We use $k_0$ to enforce the stated mean subtraction; using $k_P$ gives the usual ensemble-zero-mean formulation and the same likelihood derivation.

Let $K_{ij}=k_0(t_i,t_j)$ and $R=\mathrm{diag}({\sigma }_1^2,\dots ,{\sigma }_N^2)$. The prior latent vector is $f\sim N(0,K)$ and the independent Gaussian noise is $\epsilon \sim N(0,R)$, so $y=f+\epsilon \sim N(0,V)$ with $V=K+R$. The Gaussian-process marginal likelihood isPositive measurement variances make $V$ positive definite even if $K$ is singular. Maximize $\ell (\mathcal{H})=-\frac{1}{2}{y}^T{V}^{-1}y-\frac{1}{2}\log |V|-\frac{N}{2}\log (2\pi )$ over all three hyperparameters, using a broad search in $P$ to find competing aliases, followed by joint optimization. Cholesky decomposition evaluates the likelihood without explicitly forming an inverse.

For a well-resolved interior maximum, let $J=-{\nabla }^2\ell (\hat{\mathcal{H}})$ be the Observed Fisher information in the coordinates $(A,\ell ,P)$. Then $\boxed{\hat{P}=(\hat{\mathcal{H}}{)}_P,{\sigma }_P\approx \sqrt{(J^{-1}{)}_{PP}}}$. Equivalently, the profile-likelihood curvature in $P$ gives the same local nuisance-adjusted variance; keeping the other hyperparameters fixed would generally underestimate it. A profile interval with ${\ell }_{\mathrm{prof}}(\hat{P})-{\ell }_{\mathrm{prof}}(P)=1/2$ is a local $1\sigma$ approximation. If the period likelihood is multimodal or poorly constrained, fit the complete posterior with proper hyperparameter priors and report its modes and marginal credible intervals rather than a single Hessian error bar. The sampling pattern can create period aliases that a single local search misses.

For the first $i$ observations, writeBy Gaussian conjugacy for a normal linear model, the prefix posterior isCompute a Cholesky decomposition of $A_0={\Sigma }^{-1}$ once. If $x_i^T$ is row $i$ of the design matrix, thenThe Rank-one Cholesky update obtains a triangular factor $A_i=L_i{L}_i^T$ from $L_{i-1}$ in $O(p^2)$ operations. Two triangular solves give $m_i=A_i^{-1}{b}_i$, and, for $z_i\sim N(0,I_p)$, another solve givesThe initial factorization costs $O(p^3)$ and all $n$ updates and samples cost $O(n{p}^2)$. This is within the requested $O(p^3+n{p}^2+n^{2}p)$ bound.

Put $z_i=\log Y_i$. The Weighted graph Laplacian $L_J$ of the tree is defined byMultiplication of the Gaussian likelihood by the prior shows that, conditionally on the precision parameter $\tau$,Completing the square therefore givesAs a function of $\tau$, the posterior density isso, in shape-rate notation,The precision matrix $M$ has the sparsity pattern of a tree. A sparse Cholesky decomposition and its triangular solves have $O(n)$ cost and storage on this graph, while the gamma update also costs $O(n)$. Hence each systematic-scan Gibbs sampler iteration costs $O(n)$.

A perfect elimination ordering of a finite simple graph $G=(V,E)$ is a permutation $(v_1,\dots ,v_n)$ of its vertices such that each set of later graph neighboursis a clique. Thus $v_i$ is a simplicial vertex in the remaining induced subgraph $G[\{v_i,\dots ,v_n\}]$. Empty and one-vertex sets satisfy the clique condition automatically. The order here is the order of deletion: $v_1$ goes first.

The characterization is powerful: a finite simple graph is a chordal graph if and only if it has a perfect elimination ordering. For one proof outline, the earliest vertex of an induced cycle of length at least four would have two later graph neighbours on that graph cycle that are not adjacent, contradicting the clique condition. Conversely, every nonempty chordal graph has a simplicial vertex, and every induced subgraph of a chordal graph is a chordal graph; repeatedly deleting such a vertex supplies the ordering.^[ref]

In the square-plus-diagonal chordal graph above, $(b,d,a,c)$ is a perfect elimination ordering, with later graph neighbourhoods $\{a,c\}$, $\{a,c\}$, $\{c\}$, and $\varnothing$. Starting instead with $a$ fails: its graph neighbours $b,c,d$ do not form a clique, because $bd$ is absent. Thus even a chordal graph can have a poor elimination ordering.

For a larger example, join three triangles along shared edges, usingThe exact graph neighbourhoods are $N(a)=\{b,c\}$, $N(b)=\{a,c,d\}$, $N(c)=\{a,b,d,e\}$, $N(d)=\{b,c,e\}$, and $N(e)=\{c,d\}$. The ordering $(a,b,c,d,e)$ has later graph neighbourhoods $\{b,c\}$, $\{c,d\}$, $\{d,e\}$, $\{e\}$, and $\varnothing$, all cliques; this certifies that the graph is a chordal graph without enumerating its graph cycles. Its maximal cliques $\{a,b,c\}$, $\{b,c,d\}$, $\{c,d,e\}$ form a junction tree in that order, with intersections $\{b,c\}$ and $\{c,d\}$.

To find an ordering, maximum cardinality search starts with all scores zero, repeatedly selects an unselected vertex of largest score, and increases each unselected graph neighbour's score by one. Reverse the selection order to obtain a candidate perfect elimination ordering. For the three-triangle graph, one valid selection sequence is $(e,d,c,b,a)$, with scores at selection $0,1,2,2,2$; reversing it gives the displayed deletion order. On a chordal graph every tie choice works. On an arbitrary graph, test the resulting later graph neighbourhoods for the clique condition to recognize chordal graphs. Suitable adjacency lists, score buckets and a linear-time verification method give $O(|V|+|E|)$ recognition.^[ref]

The deletion rule also explains sparse Gaussian elimination. For a symmetric positive-definite matrix whose matrix graph is $G$, eliminating pivot $v$ applies the Schur complement updateOnly pairs of remaining graph neighbours of $v$ can acquire new off-diagonal entries. A perfect elimination ordering already has all those edges, so Cholesky decomposition creates no symbolic fill-in. Positive definiteness ensures nonzero pivots in exact arithmetic. Special numerical cancellation can suppress predicted entries, and floating-point rounding affects their values.^[ref] In the three-triangle graph, deleting $c$ first instead connects every pair in $\{a,b,d,e\}$ and adds exactly $ad,ae,be$. The graph was already a chordal graph; the extra fill-in comes from the ordering.

One further reward is optimal graph coloring. Process a perfect elimination ordering backwards and give each vertex the smallest positive color absent from its already colored graph neighbours. Those graph neighbours form a clique, so this greedy algorithm uses at most the clique number $\omega (G)$ colors; any clique of that size requires at least that many. In the three-triangle graph, coloring $(e,d,c,b,a)$ gives colors $(1,2,3,1,2)$, so both the chromatic number and the clique number are three. Every maximal clique also occurs among $\{v_i\}\cup N_i^{+}$: take its earliest vertex and use maximality. The same ordering therefore supports graph coloring, maximal clique extraction and sparse computation.

Historically, Donald J. Rose, Robert E. Tarjan and George S. Lueker's 1976 paper connected graph elimination to symmetric sparse matrices and gave a search-based $O(|V|+|E|)$ algorithm for finding a perfect elimination ordering when one exists. Its abstract distinguishes a minimal elimination ordering from a minimum one: removing avoidable fill-in does not by itself minimize the total number of added edges.^[ref]

Given a Cholesky decomposition $A=L{L}^T$, a rank-one Cholesky update computes a triangular factor of $A+x{x}^T$ in $O(n^2)$ operations without refactorizing the matrix from scratch.

Let $M=\left(\begin{array}{cc}A& B\\ B^T& D\end{array}\right)$ be a real symmetric matrix with $A$ a positive-definite matrix. Its quadratic form satisfies the completing the square identityFor each fixed vector $y$, the unique minimizing vector is $x=-A^{-1}By$, so the minimized value is $y^{T}Sy$. Also, $M$ is a positive-definite matrix exactly when $S$ is a positive-definite matrix, under the stated assumption on $A$.^[ref]

An original scalar example isHere $A=2$, $B=1$, $D=3$, and the Schur complement is $5/2$. Holding $x=0$ would give $3y^2$, but letting $x$ relax to $-y/2$ reduces the quadratic form to $(5/2)y^2$. At $y=2$ the respective values are $12$ and $10$. Eliminating a variable therefore changes the effective cost of the retained variable.

This interpretation supports quadratic optimization and the positive-definite symmetric matrix tests used in Cholesky decomposition. In a multivariate normal distribution, a covariance matrix also gives a conditional covariance through a Schur complement; the required probabilistic hypotheses are supplied by conditional multivariate normal distribution, rather than by the algebra alone.

Take a star graph $G$ with center $c$ and four leaves $1,2,3,4$. Let $L_G$ be its Laplacian matrix and $I$ the identity matrix. In the order $(c,1,2,3,4)$, the original example isFor a nonzero vector $u$, its quadratic form isThus $A$ is a symmetric positive-definite matrix and either ordering below admits a Cholesky decomposition. Changing the ordering changes the work, rather than the mathematical solvability.

Center first. Eliminating $c$ with pivot element $5$ leaves the Schur complementEvery pair of leaves now has coupling $-1/5$: six new edges, hence six undirected fill-in positions. The four remaining vertices form a clique. In the Cholesky decomposition, the first column has $C_{cc}=\sqrt{5}$ and $C_{ic}=-1/\sqrt{5}$. The rest of the lower triangular matrix is dense. To check that later cancellation does not remove its entries, after $r$ leaves have also been eliminated, the active leaf block isIndeed a leaf step sends $\alpha$ to $\alpha +{\alpha }^2/(2-\alpha )$. All active off-diagonal entries remain negative. The successive pivot elements in ordinary symmetric Gaussian elimination, equivalently the squared diagonals in the Cholesky decomposition, areThe Cholesky decomposition therefore stores $5+4+3+2+1=15$ nonzero entries, including its diagonal.

Leaves first. Permute to $(1,2,3,4,c)$. Each leaf has only one remaining neighbor, so its elimination changes only the center's diagonal, reducing it by $(-1{)}^2/2=1/2$. The successive pivot elements are $2,2,2,2,3$, and the exact Cholesky decomposition isThere is no fill-in, and only $5+4=9$ nonzero entries in $C$. This is a concrete instance of leaf elimination of a tree-pattern positive-definite matrix; its general proof explains why the same idea works on every tree pattern. The minimum degree algorithm also chooses a leaf at every nontrivial stage of this particular example, but that success gives no general optimality guarantee.

The input has 13 nonzero matrix elements when both symmetric halves are counted, or nine in its lower triangle. The six added undirected edges correspond to six added positions in one triangular factor, or 12 positions if both symmetric halves of the filled pattern are displayed. Comparing all 13 input entries directly with the 15 entries of $C$ would mix counting conventions.

Sparse Gaussian elimination solves a linear system by Gaussian elimination while exploiting its sparse matrix structure to avoid storing zeros and performing unnecessary arithmetic operations. The catch is that zeros in the input need not remain zero: eliminating a shared unknown can couple two equations that previously had no direct coupling. These new positions are fill-in, and their number can depend strongly on the order of elimination.

For a real symmetric positive-definite matrix, the usual direct method is a Cholesky decomposition. Choose an ordering, use symbolic factorization to allocate the predicted factor entries, compute their values, then solve two triangular systems. Compressed sparse storage makes the reduced storage useful. General LU decomposition may also need numerical partial pivoting, so an ordering chosen for sparsity can change during factorization.^[ref]

For a fixed ordering, let $P$ be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here $C$ is the lower triangular matrix in the Cholesky decomposition of $B$; $z=Px$. Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because $v^{T}Bv=(P^{T}v{)}^{T}A(P^{T}v)>0$ for every nonzero vector $v$. A row permutation alone generally loses the symmetric matrix structure.

The local mechanism is a Schur complement. If the active pivot element is $a_{kk}$, then for remaining indices $i,j$,Even when $a_{ij}=0$, two nonzero couplings through $k$ make the second term nonzero. Thus the elimination graph removes $k$ and joins its remaining neighbors into a clique. The fill-path criterion for symmetric elimination extends this local rule across several steps. The elimination tree organizes the resulting dependencies; the minimum degree algorithm and nested dissection choose orderings to control them.

This connection between graphs and linear systems was already explicit in Donald J. Rose, R. Endre Tarjan and George S. Lueker's 1976 study of fill-in and perfect elimination orderings.^[ref]

A Hermitian matrix $A$ is a positive-definite matrix exactly when its leading principal minorsare all positive. The leading principal minor uses the first $k$ rows and the first $k$ columns in the same ordering. For the two-by-two Cholesky decomposition example, ${\Delta }_1=4$ and ${\Delta }_2=4\cdot 5-2^2=16$, so the criterion proves positive definiteness without calculating eigenvalues.

The successive pivot elements before taking square roots are ${\Delta }_k/{\Delta }_{k-1}$, with ${\Delta }_0=1$. Here they are $4$ and $16/4=4$. In general, a leading triangular matrix factor has determinant equal to the product of its diagonal entries, soConversely, positive leading principal minors make each successive Schur complement pivot element positive, allowing the Cholesky decomposition to be constructed. The identity $u^{T}Au=\Vert L^{T}u{\Vert }_2^2$ then proves positive definiteness; for complex matrices, replace the transposes by conjugate transposes. This gives a short inductive proof of the criterion.

For $B=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$, the first minor is positive but $\det B=-3$. The second Cholesky radicand would be $1-2^2=-3$, and $v=(1,-1{)}^T$ directly gives $v^{T}Bv=-2<0$. Thus positive diagonal entries are insufficient. Replacing “positive” by “nonnegative” in just the leading-minor test is also insufficient for positive semidefiniteness: $\mathrm{diag}(0,-1)$ has leading minors $0,0$, but its quadratic form is negative on $(0,1{)}^T$.