## 2 Materials and Methods
### Online Network Topology Inference
#### 2.2.1 Algorithm Construction  
Our algorithm construction approach entails two steps per time instant \(t=1,2,\ldots\), where we: (i) recursively update the observations' covariance matrix \(\hat{\mathbf{C}}_{\mathbf{y},t}\) in \(\mathcal{O}(N^{2})\) complexity; and then (ii) run a single iteration of the batch graph learning algorithm developed in Section 2.1.3 to solve (13) efficiently. Different from recent approaches that learn dynamic graphs from the observation of smooth signals [32; 33], the resulting algorithm's memory storage requirement and computational cost per data sample \(\mathbf{y}_{t}\) does not grow with \(t\). A similar idea to the one outlined in (ii) was advocated in [16] to develop an online sparse subspace clustering algorithm; see also [37] for dynamic SEM estimation from traces of information cascades. Step (i) is straightforward, and the sample covariance \(\hat{\mathbf{C}}_{\mathbf{y},t-1}\) is recursively updated once \(\mathbf{y}_{t}\) becomes available through a rank-one correction as follows  
\[\hat{\mathbf{C}}_{\mathbf{y},t}=\frac{1}{t}\left((t-1)\hat{\mathbf{C}}_{ \mathbf{y},t-1}+\mathbf{y}_{t}\mathbf{y}_{t}^{T}\right). \tag{14}\]  
This so-termed infinite memory sample estimate is appropriate for time-invariant settings, i.e., when the graph topology remains fixed for all \(t\). To track dynamic graphs, it is prudent to eventually forget about past observations (cf. (14) incorporates all signals \(\{\mathbf{y}_{\tau}\}_{\tau=1}^{t}\)). This can be accomplished via exponentially-weighted empirical covariance estimators or by using a (fixed-length) sliding window of data, both of which can be updated recursively via minor modifications to (14). Initialization of the covariance estimate \(\hat{\mathbf{C}}_{\mathbf{y},0}\) can be performed in practice via sample averaging of a few signals collected before the algorithm runs, or simply as a scaled identity matrix. To solve (13) online by building on the insights gained from the batch solver (cf. step (ii)), we let iterations \(k=1,2,\ldots\) in Algorithm 1 coincide with the instants \(t\) of data acquisition. In other words, at time \(t\) we run a single iteration of (11) to update \(\mathbf{S}_{t}\) before the new datum \(\mathbf{y}_{t+1}\) arrives at time \(t+1\). Specifically, the online PG algorithm takes the form  
\[\mathbf{S}_{t+1}:=\text{prox}_{\gamma_{t}\|\cdot\|_{1},\mathcal{S}}\big{(} \mathbf{S}_{t}-\gamma_{t}\
abla g_{t}(\mathbf{S}_{t})\big{)}, \tag{15}\]where the step size \(\gamma_{t}\) is chosen such that \(\gamma_{t}<\frac{2}{M_{t}}=\frac{1}{2\mu\lambda_{\max}^{2}(\mathbf{C}_{y,t})}\). Recall that the gradient \(\
abla g_{t}(\mathbf{S}_{t})\) is given by (9), and it is a function of the updated covariance matrix \(\hat{\mathbf{C}}_{y,t}\) (cf. (14)). The proximal operator for the \(\ell_{1}\)-norm entails the pointwise nonlinearity in (12), with a threshold \(\gamma_{t}\) that will in general be time varying. If the signals arrive faster, one can create a buffer and perform each iteration of the algorithm on a \(\hat{\mathbf{C}}_{y,t}\) updated with a sliding window of all newly observed signals (in a way akin to processing a minibatch of data). On the other hand, for a slower arrival rate additional PG iterations during \((t-1,t]\) would likely improve recovery performance; see also the discussion following Theorem 1. The proposed online scheme is tabulated under Algorithm 2; the update of \(\hat{\mathbf{C}}_{y,t}\) can be modified to accommodate tracking of dynamic graph topologies. ```
0:\(\{\mathbf{y}_{1},\dots,\mathbf{y}_{t},\mathbf{y}



alternating-minimization algorithm in [14]. The merits of working with the inverse problem (6) are outlined in Section 2.1.1. Moreover, enforcing some of the admissibility constraints in \(\mathcal{S}\) requires an inner ADMM loop to compute nontrivial projection operators, which could hinder applicability in delay-sensitive environments [13]. Neither of these schemes offers convergence guarantees to the solutions of the resulting time-varying optimization problems.