## 2 Standard Projection-Based Approach for Data Reconstruction
However, using \(k>m\) is impossible if we follow the standard DEIM approximation and use \(\mathbf{V}_{c}\) as an input to Algorithm 3, because \(\mathbf{V}_{c}\) has only \(k\) columns, which implies Algorithm 3 can give, at most, \(k\) indices. To resolve this issue, instead of using \(\mathbf{V}_{c}\) directly, we will consider a matrix constructed from the full set of the POD basis for the complete snapshot matrix \(\mathbf{Y}\) with rows selected from the indices of the known components. In particular, if we define \(\mathbf{\tilde{V}}\in\mathbb{R}^{n\times r}\) to be the left singular matrix from SVD of the complete snapshot matrix \(\mathbf{Y}\), where \(r=rank(\mathbf{Y})\), the input to Algorithm 3 would be the matrix obtained from \(\mathbf{\tilde{V}}\) with rows corresponding to the complete components, i.e.,

\[\mathbf{\tilde{V}}_{c}:=\mathbf{C}^{T}\mathbf{\tilde{V}}\in\mathbb{R}^{n_{c} \times r}, \tag{8}\]

which comes from \(\mathbf{\tilde{V}}\) with selected rows corresponding to the \(n_{c}\) known components in \(\mathcal{C}\). In this case, we can use the DEIM algorithm to select up to \(r\) indices that correspond to the most (\(r\)) relevant components of the reconstruction problem in (1). Note that the columns in \(\mathbf{V}\) are the first \(k\) columns in \(\mathbf{\tilde{V}}\). Suppose \(\mathbf{\tilde{V}}_{c}\in\mathbb{R}^{n_{c}\times r}\) has \(r\) linearly independent columns with \(r\leq n_{c}\). Then, the columns of \(\mathbf{\tilde{V}}_{c}\) can be used in Algorithm 3 to select \(m\) DEIM indices, where \(m\leq r\). In this case, suppose \(\wp_{1},\wp_{2},\dots,\wp_{m}\) are the output indices of DEIM Algorithm 3 and let \(\mathbf{P}=[\mathbf{e}_{\wp_{1}},\dots,\mathbf{e}_{\wp_{m}}]\in\mathbb{R}^{n_ {c}\times m}\) as defined earlier in this section. Vector \(\mathbf{a}\) in (1) can be computed from a smaller least-squares problem:

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

Note that we have assumed that \(\mathbf{\tilde{V}}_{c}\in\mathbb{R}^{n_{c}\times r}\) has linearly independent columns, which may not hold in general cases. To avoid this assumption, we can apply SVD to the matrix \(\mathbf{\tilde{V}}_{c}\) and use the set of first \(m\) corresponding left singular vectors as an input to the DEIM Algorithm 3. The accelerated POD-LS steps are summarized in Algorithm 4 for both cases of (i) using \(\mathbf{\tilde{V}}_{c}\) directly as an input and (ii) using the set of left singular vectors of \(\mathbf{\tilde{V}}_{c}\) as an input to Algorithm 3 for selecting the most (\(m\)) important components. Note that, aslater shown in the numerical tests, the reconstruction results using case (ii) may not be as accurate as the ones using case (i). ```
0:- Complete snapshot set \(\{\mathbf{y}_{j}\}_{j=1}^{n_{s}}\subset\mathbb{R}^{n}\) and, dimension \(k\leq rank(\{\mathbf{y}_{j}\}_{j=1}^{n_{s}})\) - Incomplete data \(\widehat{\mathbf{y}}\in\mathbb{R}^{n}\) with known entries \(\widehat{y}_{j}\), \(j\in\mathcal{C}\) and unknown entries \(\widehat{y}_{j}\), \(j\in\mathcal{G}\)
```
0:- Approximation: \(\widehat{\mathbf{y}}_{g}=[\widehat{y}_{j}]\), \(j\in\mathcal{G}=\{g_{1},g_{2},\ldots,g_{n_{g}}\}\)
1:Create snapshot matrix : \(\mathbf{Y}=[\mathbf{y}_{1},\ldots,\mathbf{y}_{n_{s}}]\in\mathbb{R}^{n\times n _{s}}\)and let \(r=rank(\mathbf{Y})\). 2:Compute POD basis \(\mathbf{V}\) of rank \(k\leq r\) for \(\mathbf{Y}\) from rSVD in Algorithm 2. 3:Find coefficient vector \(\mathbf{a}\) 3.1 Find indices \(\widehat{\wp}=[\wp_{1},\ldots,\wp_{m}]^{T}\in\mathbb{R}^{m}\) and \(\mathbf{P}\) from Algorithm 3 by using input from either (i) \(\widehat{\mathbf{V}}_{c}\) defined in (8), or (ii) Left singular vectors of \(\mathbf{V}_{c}\) using SVD or rSVD 3.2 Solve \(\mathbf{a}\) from (9): \(\min_{\mathbf{a}\in\mathbb{R}^{n}}\|\mathbf{P}^{T}\widehat{\wp}_{c}-\mathbf{P }^{T}\mathbf{V}_{c}\mathbf{a}\|_{2}^{2}\). 4:Compute the approximation \(\widehat{\mathbf{y}}_{g}~{}\approx~{}\mathbf{V}_{g}\mathbf{a}\).