## 3 Construction of Measurement Matrix by Cyclic Direct Product and QR Decomposition
### Construction of Measurement Matrix Based On Cyclic Direct Product and QR Decomposition  
As stated in Section 3.1, a high-dimension matrix could be constructed by taking the direct product, and applied to the computation of the measurement matrix for CS, i.e., the formation of a high-dimension orthogonal column vector set by finite times of cyclic direct product operation on lower-dimension orthogonal \"seed\" vectors, yielding a matrix with orthogonal column vectors. \(M\) rows are selected from this matrix to afford the corresponding deterministic measurement matrix. However, the high-dimension column vector set could only ensure mutual independence among the columns of the matrix thus formed, while the elements of the column vectors were still highly similar When an appropriate number of measurements \(M\) is used for the construction of the measurement matrix, the column vectors may lose their pairwise orthogonality. As described in the introduction, the measurement matrix should possess column vectors with the highest possible linear independence. In an orthogonal matrix, the number of rows is far less than the number of columns. As determined by its structure, the maximum rank of a measurement matrix thus equals the number of rows, which means that linear correlation necessarily exists for this class of matrix.  
The solution to the above problems lies in reducing the correlation between the column vectors. QR decomposition [31] of a matrix increases the singular value of the matrix without altering the properties of the measurement matrix, thus bringing the column vectors closer to being linearly independent. Specifically, QR decomposition is applied to the matrix composed of the set of higher-dimension orthogonal column vectors to obtain an orthogonal matrix, whose corresponding rows are selected to construct the measurement matrix. The detailed steps are shown in Figure 2.  
Step 1. Suitable low-dimension orthogonal \"seed\" vectors are selected. The number of these vectors is equal to its dimension \(N\). In the ideal case, the matrix \(U\) formed by these \"seed\" vectors is an orthogonal matrix with \(U*U^{T}\) = \(E\), where \(E\) is the identity matrix. One example of \(U\) is \(\left[\begin{array}{cc}1&1\\ 1&-1\end{array}\right]\), which meets the required pairwise orthogonality among the row vectors and column vectors.  
Step 2. The number of cyclic direct product computations, \(k\approx\) log\({}_{n}\)\(N\), is calculated using the dimension \(n\) of the \"seed\" vector and the dimension \(N\) of the higher-dimension column vectors, giving the initial value \(R_{1}\) = \(U\), \(R_{i}\) = \(R_{i-1}\otimes U\), while \(i\) = 2, 3,..., \(k\).  
Step 3. The matrix \(R_{k}\) obtained after \(k\) cycles is a matrix of the order \(N\) with mutually orthogonal row vectors and column vectors. By theorems related to the QR decomposition of matrix analysis, an orthogonal matrix can be obtained by decomposition.  
Step 4. \(M\) (\(M\) is the number of measurements) rows are selected from \(U_{k}\) to give the measurement matrix, i.e., the matrix by the QR decomposition of the cyclic direct product.  
\(\Phi=U_{k}(c,\cdot)\), in which \(c\) is the set of subscripts for the rows selected, and \(\Phi\) is the measurement matrix generated by the QR decomposition of the cyclic direct product.  
Step 5. The measurement matrix is normalized in conformance to the RIP.  
After the above procedures, the non-correlation among the column vectors of the measurement matrix formed by the cyclic product and QR decomposition is significantly improved. QR decomposition increases the least singular value of the matrix and further enhances its nonlinearity and independence, fulfilling the criteria for the measurement matrix. From the matrix theory, the measurement matrix constructed by QR decomposition satisfies the RIP. This measurement matrix given by the cyclic direct product and QR decomposition is deterministic, which greatly facilitates its engineering and implementation.