## 2 Standard Projection-Based Approach for Data Reconstruction
```
1:\(\{\mathbf{y}_{\ell}\}_{\ell=1}^{n_{s}}\subset\mathbb{R}^{n}\), \(k\) where \(k\leq rank(\{\mathbf{y}_{\ell}\}_{\ell=1}^{n_{s}})\)
2:OTPUT: POD basis: \(\mathbf{U}_{k}\), Singular values: \(\mathbf{S}_{k}\)
3: Form \(\mathbf{Y}=[\mathbf{y}_{1},\mathbf{y}_{2},\dots,\mathbf{y}_{n_{s}}]\)
4: Construct random matrix \(\Omega=rand(M,K_{0})\), \(K_{0}=k+p\), where \(p\) is a positive integer
5:\(\mathbf{Q}=orthog(\mathbf{Y}\Omega)\)
6: Set \(\mathbf{B}=\mathbf{Q}^{T}\mathbf{Y}\in\mathbb{R}^{K_{0}\times n_{s}}\)
7: Compute SVD of \(\mathbf{B}\): \(\mathbf{B}=\hat{\mathbf{U}}\hat{\Sigma}\hat{\mathbf{V}}^{T}\)
8: Basis: \(\mathbf{U}=\mathbf{Q}\hat{\mathbf{U}}\)
9: Truncation: \(\mathbf{U}_{k}=\mathbf{U}(\cdot,1:k)\), \(\mathbf{S}_{k}=\Sigma(\cdot,1:k)\)
```
**Algorithm 2** Randomized Singular Value Decomposition (rSVD)

## 5 Accelerated POD-LS Method (Gappy POD)

This section aims to discuss an efficient approach that can reduce the computational complexity for solving the standard LS approach (LS-POD approach) used in the data reconstruction technique described in Section 2. A greedy-based approach called the discrete empirical interpolation method (DEIM) is first discussed. Then, two variants of missing data approximations using DEIM are later introduced. ### Discrete Empirical Interpolation Method (DEIM)

DEIM was first introduced for the purpose of approximating the nonlinear term in the differential equations [35]. In this work, the interpolation indices from this method will be used to reduce the computational complexity of solving the least-squares approximation inStep 3 of Algorithm 1. This section describes DEIM in a general setting and provides the corresponding greedy algorithm for selecting _important_ components that can be used in the approximation. Consider a vector \(\mathbf{f}\in\mathbb{R}^{n}\). For a given orthonormal matrix \(\mathbf{U}\in\mathbb{R}^{n\times m}\) with \(m\leq n\), an approximation of this vector \(\mathbf{f}\) obtained from projecting onto the subspace \(\text{span}\{\mathbf{U}\}\) is given by

\[\mathbf{f} \approx \mathbf{U}\mathbf{d}, \tag{6}\]

for some vector \(\mathbf{d}\in\mathbb{R}^{m}\). The vector \(\mathbf{d}\) can be obtained by using an interpolation method. That is, it can be solved from a square system that extracts only \(m\) rows of (6). In particular, suppose \(\wp_{1},\wp_{2},\dots,\wp_{m}\) are the indices of the selected components in \(\mathbf{f}\) and define \(\mathbf{P}=[\mathbf{e}_{\wp_{1}},\dots,\mathbf{e}_{\wp_{m}}]\in\mathbb{R}^{n \times m}\), where \(\mathbf{e}_{\wp_{1}}=[0,\dots,0,1,0,\dots,0]^{T}\in\mathbb{R}^{n}\) is the \(\wp_{i}\)-th column of the identity matrix \(\mathbf{I}_{n}\in\mathbb{R}^{n\times n}\), for \(i=1,\dots,m\). Note that, as in the previous section, pre-multiplying \(\mathbf{P}^{T}\) is equivalent to extracting the \(m\) rows corresponding to the interpolation indices \(\wp_{1},\dots,\wp_{m}\). The coefficient vector \(\mathbf{d}\) in the DEIM approximation solves the following minimization problem

\[\min_{\mathbf{d}\in\mathbb{R}^{m}}\|\mathbf{P}^{T}\mathbf{f}-\mathbf{P}^{T} \mathbf{U}\mathbf{d}\|_{2}^{2},\]

which gives \(\mathbf{d}=(\mathbf{P}^{T}\mathbf{U})^{+}\mathbf{P}^{T}\mathbf{f}\), where \((\mathbf{P}^{T}\mathbf{U})^{+}=[(\mathbf{P}^{T}\mathbf{U})^{T}(\mathbf{PU})]^ {-1}(\mathbf{P}^{T}\mathbf{U})^{T}\) is the pseudo-inverse of \(\mathbf{P}^{T}\mathbf{U}\). Notice that \(\mathbf{P}^{T}\mathbf{U}\) is a square matrix of size \(m\times m\). When the indices \(\wp_{1},\dots,\wp_{m}\) are selected by the DEIM procedure given in Algorithm 3, it was shown in [35] that \(\mathbf{P}^{T}\mathbf{U}\) is invertible. i.e., \((\mathbf{P}^{T}\mathbf{U})^{+}=(\mathbf{P}^{T}\mathbf{U})^{-1}\), and the approximation in (6) for \(\mathbf{f}\) becomes

\[\min_{\mathbf{a}\in\mathbb{R}^{k}}\|\widehat{\mathbf{y}}_{c}-\mathbf{V}_{c} \mathbf{a}\|_{2}^{2}. \tag{1}\]0

This approximation (7) is called the DEIM approximation.