## 4 Algorithm for Solving Optimization Problem  
In Section 3, we derived a novel objective function that calculates the mutual coherence with lower computational complexity than the typical Gram matrix computation. In this section, we use the Hadamard matrix as a unitary matrix, i.e., \(\mathbf{U}=\mathbf{H}_{p}\) for the Kronecker product. We use an existing algorithm, Algorithm 2 in [41], to solve the optimization problem (16) to find a subsampling index set for the Kronecker-product-based frame with low mutual coherence. We give a brief sketch of Algorithm 2 in [41], and readers are referred to [41] for more details. Since the objective function of (16) is non-convex, we relax the binary constraint of \(\tilde{\mathbf{B}}\) by finding \(\tilde{\mathbf{X}}\in\mathbb{R}^{q\times p}\) instead with the elements between \(0\) and \(1\), similar to the relaxation of [41]. Then, we begin with an optimization problem, which is based on IRL1 [42], given as  
\[ \begin{split}\min_{\widetilde{\mathbf{X}}}\mathcal{M}(m^{-1} \mathbf{F}_{q}^{H}\cdot\widetilde{\mathbf{X}}\cdot\mathbf{H}_{p}-\mathbf{E}_{ 1})+\lambda\Big{\|}\text{diag}(\mathbf{w})\cdot\text{vec}(\widetilde{ \mathbf{X}})\Big{\|}_{1}\\ \text{subject to }\widetilde{x}_{1}=1,\,\sum_{i=2}^{N} \widetilde{x}_{i}=m-1,\,0\leq\widetilde{x}_{i}\leq 1,\,\widetilde{x}_{k}=0,k\in \Omega_{0},\end{split}  \tag{17}\]  
where \(\lambda\) is a regularization parameter and \(\text{vec}(\widetilde{\mathbf{X}})=[\widetilde{x}_{1},\cdots,\widetilde{x}_{ N}]^{T}\). To obtain a stable solution of (17), some elements of \(\widetilde{\mathbf{X}}\) at random positions are fixed to zero. The index set of positions fixed to zero is denoted as \(\Omega_{0}\subset\{2,3,\cdots,N\}\), where \(|\Omega_{0}|=\lceil\zeta(N-m)\rceil\) for \(0<\zeta<1\). Moreover, \(\widetilde{x}_{1}\) is fixed to \(1\) for a unique solution. In (17), the \(l_{1}\) weight regularization term \(\Big{\|}\text{diag}(\mathbf{w})\cdot\text{vec}(\widetilde{\mathbf{X}})\Big{\|} _{1}\) promotes the sparsity of \(\widetilde{\mathbf{X}}\), where \(\mathbf{w}=[w_{1},\cdots,w_{N}]^{T}\) with each element used in Algorithm 2 [41], i.e.,  
\[w_{k}=(\widetilde{x}_{k}+\epsilon)^{-1}. \tag{18}\]  
We solve this optimization problem via CVX [48]. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Objective Function** & **Computational Complexity** & **Components of Kronecker Product** \\ \hline (9) & \(O(mN^{2})\) & General matrices \\ (11) & \(O(N(p^{2}+p\log q))\) & Unitary and Fourier matrices \\ (16) & \(O(N\log N)\) & Hadamard and Fourier matrices \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The computational complexities of several objective functions for the frames from Kronecker product, where \(N=pq\). Next, we quantize the solution of (17) to obtain the binary solution \(\widetilde{\mathbf{B}}\). Let \(\operatorname{vec}(\widetilde{\mathbf{B}})=[\widetilde{b}_{1},\cdots,\widetilde{ b}_{N}]^{T}\), where each element is obtained by  
\[\widetilde{b}_{i}= \begin{cases}1,&\text{if }\widetilde{x}_{i}\geq\delta\\ 0,&\text{if }\widetilde{x}_{i}<\delta\end{cases}  \tag{19}\]  
for \(2\leq i\leq N\), and the support set of \(\operatorname{vec}(\widetilde{\mathbf{B}})\) is denoted by \(\Omega\). Note that \(\Omega\) may contain \(m\) or more indices with sufficiently small \(\delta\) in (19), which requires an additional step to reduce the number of indices to \(m\). As in Step 5 of Algorithm 2[41], we eliminate some indices iteratively until \(m\) indices remain in \(\Omega\), where an index \(i\in\Omega\) will be eliminated at each iteration if \(\Omega\setminus\{i\}\) causes the lowest increase in mutual coherence. Finally, we conduct a local brute-force search to maximally reduce the mutual coherence of the Kronecker-product-based frame, which updates \(\Omega\) by replacing its \(\beta\) indices by those in \(\{1,\cdots,N\}\setminus\Omega\). As in the previous step, the mutual coherence is computed by (16) for the local brute-force search.