## 3 Problem Formulation for Kronecker-Product-Based Frames
### Kronecker Product with Unitary Matrix  
In this section, we show that the original problem of (9) can be represented by a new equivalent problem to find a subsampling row index set \(\Omega\).  
Theorem 3.1: _Define a binary matrix \(\widetilde{\mathbf{B}}=[\widetilde{\mathbf{b}}_{1},\cdots,\widetilde{\mathbf{b }}_{p}]\in\{0,1\}^{q\times p}\), where \(\text{diag}(\widetilde{\mathbf{b}}_{k})=\mathbf{R}_{\Omega_{k}}^{T}\cdot \mathbf{R}_{\Omega_{k}}\). Moreover, define \(\mathbf{U}_{c}\) by including distinct column-wise multiplications from all possible pairs of column vectors of \(\overline{\mathbf{U}}\) and \(\mathbf{U}\), i.e.,_  
\[\mathbf{U}_{c}=[\mathbf{1}_{p},\ \overline{\mathbf{u}}_{1}\bigodot\mathbf{u}_{2}, \ \cdots,\ \overline{\mathbf{u}}_{i}\bigodot\mathbf{u}_{j},\ \cdots,\ \overline{\mathbf{u}}_{p-1}\bigodot\mathbf{u}_{p}], \tag{10}\]_where \(1\leq i<j\leq p\) and \(\mathbf{1}_{p}=\{1,\cdots,1\}^{T}\) are all one vector of length \(p\). Then, the problem (9) can be equivalently converted into_  
\[\min_{\widetilde{\mathbf{B}}\in\{0,1\}^{q\times p}}\mathcal{M}(m^{-1}\mathbf{F }_{q}^{H}\cdot\widetilde{\mathbf{B}}\cdot\mathbf{U}_{c}-\mathbf{E}), \tag{11}\]  
_where all elements of \(\mathbf{E}=[e_{i,j}|1\leq i\leq q,1\leq j\leq p]\) are zero except \(e_{1,1}=1\)._  
**Proof of Theorem 1.** For convenience of analysis, we assume that the selected row indices of \(\Omega\) are sorted in ascending order. Recall \(\mathbf{R}_{\Omega}=[\mathbf{R}_{\Omega_{1}},\cdots,\mathbf{R}_{\Omega_{p}}]\), where \(\mathbf{R}_{\Omega_{i}}\in\{0,1\}^{m\times q}\). Then, we can write the Gram matrix \(\mathbf{G}\) using submatrices \(\mathbf{G}_{i,j}\), i.e., \(\mathbf{G}=[\mathbf{G}_{i,j}|1\leq i,j\leq p]\), where  
\[\mathbf{G}_{i,j}=\sum_{k=1}^{p}\sum_{l=1}^{p}u_{l,j}^{*}\mathbf{F}_{q}^{H} \cdot\mathbf{R}_{\Omega_{l}}^{T}\cdot\mathbf{R}_{\Omega_{k}}\cdot\mathbf{F}_ {q}. \tag{12}\]  
Since \(\mathbf{R}_{\Omega_{l}}^{T}\cdot\mathbf{R}_{\Omega_{k}}=\mathbf{0}\) for \(l\
eq k\) and \(\mathbf{R}_{\Omega_{k}}^{T}\cdot\mathbf{R}_{\Omega_{k}}=\text{diag}( \widetilde{\mathbf{b}}_{k})\), we have  
\[\mathbf{G}_{i,j}=\sum_{k=1}^{p}u_{k,j}^{*}\mathbf{u}_{k,j}\mathbf{F}_{q}^{H} \cdot\text{diag}(\widetilde{\mathbf{b}}_{k})\cdot\mathbf{F}_{q}. \tag{13}\]  
Since \(\mathbf{F}_{q}^{H}\cdot\text{diag}(\widetilde{\mathbf{b}}_{k})\cdot\mathbf{F }_{q}=\text{circ}(\mathbf{b}_{k})\), where \(\mathbf{b}_{k}=\mathbf{F}_{q}^{H}\cdot\widetilde{\mathbf{b}}_{k}\), \(\mathbf{G}_{i,j}\) in (13) becomes  
\[\mathbf{G}_{i,j}=\sum_{k=1}^{p}u_{k,j}^{*}\mathbf{u}_{k,j}\text{circ}(\mathbf{ b}_{k}). \tag{14}\]  
Thanks to the circulant feature of (14), we only need to evaluate the first column vector of each submatrix \(\mathbf{G}_{i,j}\) for mutual coherence, instead of all the columns. The first column vector of the submatrix \(\mathbf{G}_{i,j}\) can be written as  
\[\sum_{k=1}^{p}u_{k,j}^{*}\mathbf{u}_{k,j}\mathbf{b}_{k}=\sum_{k=1}^{p}u_{k,i} ^{*}\mathbf{u}_{k,j}\mathbf{F}_{q}^{H}\widetilde{\mathbf{b}}_{k}=\mathbf{F}_ {q}^{H}\cdot\widetilde{\mathbf{B}}\cdot(\overline{\mathbf{u}}_{i}\bigodot \mathbf{u}_{j}), \tag{15}\]  
where \(\widetilde{\mathbf{B}}=[\widetilde{\mathbf{b}}_{1},\cdots,\widetilde{\mathbf{ b}}_{p}]\in\{0,1\}^{q\times p}\). Moreover, we only need to check the submatrices \(\mathbf{G}_{i,j}\) for \(1\leq i\leq j\leq p\), since the Gram matrix \(\mathbf{G}\) is symmetric in its magnitude. Note that \(\overline{\mathbf{u}}_{i}\bigodot\mathbf{u}_{i}=\mathbf{1}_{p}\) for all \(i\), as each element of \(\mathbf{U}\) has unit magnitude. To evaluate the mutual coherence, it is thus sufficient to check the first column vectors of \(\mathbf{G}_{i,j}\) in (15) only for the column-wise multiplications in \(\mathbf{U}_{c}\). As a result, the original problem (9) to find a subsampling index set \(\Omega\) can be equivalently represented by (11). \(\square\)