## 2 Standard Projection-Based Approach for Data Reconstruction
The sets of indices \(\{\wp_{1},\wp_{2},\dots,\wp_{m}\}\) are obtained by the DEIM index selection algorithm [35], shown in Algorithm 3, which is a greedy procedure that aims to capture the variation of the spatial behavior of the input basis using the infinity norm. ```
1:\(\{\mathbf{u}_{\ell}\}_{\ell=1}^{m}\subset\mathbb{R}^{n}\) linearly independent
2:\(\vec{\wp}=[\wp_{1},\dots,\wp_{m}]^{T}\in\mathbb{R}^{m}\) and \(\mathbf{P}\)
3:\(\wp_{1}=\arg\max_{i=1,2,\dots,n}\{|\mathbf{u}_{i}|\}\)
4:\(\mathbf{U}=[\mathbf{u}_{1}],\mathbf{P}=[\mathbf{e}_{\wp_{1}}],\vec{\wp}=[ \wp_{1}]\);
5:for\(j=2\) to \(m\)do
6: Solve \((\mathbf{P}^{T}\mathbf{U})\mathbf{z}=\mathbf{P}^{T}\mathbf{u}_{j}\);
7:\(\mathbf{r}=\mathbf{u}_{j}-\mathbf{U}\mathbf{z}\)
8:\(\wp_{j}=\arg\max_{i=1,\dots,n}\{|\mathbf{r}_{i}|\}\)
9:\(\mathbf{U}\leftarrow[\mathbf{U}\quad\mathbf{u}_{j}],\mathbf{P}\leftarrow[ \mathbf{P}\quad\mathbf{e}_{\wp_{j}}],\vec{\wp}\leftarrow \begin{bmatrix} \vec{\wp}\\ \wp_{j}\end{bmatrix} \)
10:endfor
```
**Algorithm 3** Algorithm to create for Interpolation Indices DEIM

From Algorithm 3, DEIM selects the interpolation indices so that the approximation has the smallest error \(\mathbf{r}=\mathbf{u}_{j}-\mathbf{U}\mathbf{z}\) in each iteration \(j\). The procedure of DEIM Algorithm 3 can be described as follows. First, the input basis set \(\{\mathbf{u}_{\ell}\}_{\ell=1}^{n}\) of rank \(m\). The space spanned by this basis set, in general, is expected to approximately contain the vector \(\mathbf{f}\). Then, it selects the first index of a component in the first basis vector \(\mathbf{u}_{1}\) with the largest absolute value. Next, each of the other indices is selected from the component with the largest absolute residual error \(\mathbf{r}=\mathbf{u}_{\ell}-\mathbf{U}\mathbf{z}\) in each step. More details on DEIM approximation and its corresponding error bound can be found in [35]. Some extensions of this error bound to the state-space error estimate can be found in [36; 37]. ### Accelerated POD-LS Method by Using DEIM

This work particularly focuses on the situation when the incomplete data \(\mathbf{\tilde{y}}\) is in a high-dimensional space, i.e., the value of \(n\) is large, which may result in a large number of known components \(n_{c}\), even though there are a lot of unknown components \(n_{g}\). In this case, the main computational work in approximating missing components may occur while solving for the coefficient vector \(\mathbf{a}\) in (1) or in Step 3 of Algorithm 1. One possible way to reduce this computational work is to use only a small number of known components to specify \(\mathbf{a}\in\mathbb{R}^{k}\). These components have to be carefully selected so that they can represent all other \(n_{c}\) components and maintain the same accuracy in the approximation. For this purpose, the procedure shown in Algorithm 3 for selecting DEIM indices, which corresponde to _important_ components, will be used as described. Recall from Step 3 of Algorithm 1 that it has to solve for a vector \(\mathbf{a}\) from the following minimization problem:

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

Suppose \(\mathbf{V}_{c}\in\mathbb{R}^{n_{c}\times k}\) has linearly independent columns. Then, for a given DEIM dimension \(m\leq\min\{n_{c},k\}\), the columns of \(\mathbf{V}_{c}\) can be used as an input of Algorithm 3 to select \(m\) DEIM indices that can cover the variations of \(n_{c}\) components. In many applications, when \(n\) is much larger than the number of available complete data \(n_{s}\), i.e., \(n>n_{s}\geq k\), we have \(\min\{n,k\}=k\). Notice that, based on the standard DEIM approximation, dimension \(m\) is limited to the truncated dimension \(k\) of \(\mathbf{V}\). We can improve the accuracy of the reconstruction by further including more important components of the complete data, i.e., using dimension \(m\) that is larger than \(k\).