Chinese Journal of Electronics

Vol.25, No.3, May 2016

Block-Based Projection Matrix Design for

Compressed Sensing∗
LI Zhetao1,2,3 , XIE Jingxiong1,3 , ZHU Gengming4 , PENG Xin5 , XIE Yanrong1
and CHOI Youngjune6
(1. The College of Information Engineering, Xiangtan University, Xiangtan 411105, China)
(2. School of Computer, National University of Defense Technology, Changsha 410073, China)
(3. Key Laboratory of Intelligent Computing and Information Processing of Ministry of Education,
Xiangtan University, Xiangtan 411105, China)
(4. School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China)
(5. College of Information and Communication Engineering, Hunan Institute of Science and Technology,
Yueyang 414000, China)
(6. Department of Information and Computer Engineering, Ajou University, Suwon 443749, Korea)

Abstract — The objective of optimizing a projection imaging, digital communication and astronomy, etc.
matrix is to decrease the mutual coherence between a pro- In a CS system, the sensing matrix D is the prod-
jection matrix and a basis matrix. In this paper, a novel
block-based method is proposed to design a projection ma-
uct of the basis matrix Ψ and the projection matrix
trix in compressed sensing. Here, the projection matrix (also called measurement matrix) Φ. According to the
is divided into two blocks. The relationship between the Restricted isometry property (RIP)[4] , the incoherence be-
two blocks was obtained by reasoning and proving. The- tween Φ and Ψ implies that the sparse signal would be
oretical analysis demonstrates that the mutual coherence
between the whole projection matrix and the whole ba- reconstructed with high probability. Therefore, decreas-
sis matrix keeps as good as the mutual coherence between ing mutual coherence has caused widespread concerns in
the block matrix and blocked basis matrix. Experimental CS.
results show that the proposed method obtains better per-
In order to decrease the mutual coherence, we pro-
formance compared to existing methods.
pose a new block-based method to design the projec-
Key words — Compressed sensing, Projection matrix, tion matrix. Firstly, the projection matrix is divided into
Block optimization, Mutual coherence. two blocks, and then the relationship between the two
blocks was obtained by reasoning and proving. Theoret-
I. Introduction ical analysis and experiments demonstrate that the pro-
posed method keeps low mutual coherence and has better
Compressed sensing (CS) indicates that a signal of reconstruction performance than other methods.
length N that can be transformed into a K(K  N ) The remainder of the paper is organized as follows.
sparse signal, in a particular space, can be reconstructed Section II summarizes the state-of-the-art in projection
with high probability from O(K log N ) measurements, matrix design. Section III provides the design of block-
which is much smaller than that required by the Nyquist based projection matrix. In Section IV we make a compar-
sampling theorem[1−3] . CS has been widely used in high- ison of our work with related works through simulation.
resolution radar imaging, medical magnetic resonance Section V presents our main conclusions.
∗ Manuscript Received Apr. 24, 2014; Accepted Sept. 24, 2014. This work is supported by the National Natural Science Foundation of

China (No.61100215, No.61311140261, No.61379115, No.61372049, No.61300039), Basic Science Research Program through the National
Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (No.2012R1A1A1017284), Ministry of
Science, ICT and Future Planning of Korea under the Global IT Talent Support Program ([Link]-2014-H0904-14-1004) supervised by the
National IT Industry Promotion Agency, Hunan Provincial Natural Science Foundation of China (No.13JJ8006, No.12JJ9021, No.14JJ3130)
and the Construct Program of the Key Discipline in Hunan Province and College Students Innovation Project (No.2013XTUXJ47).
c 2016 Chinese Institute of Electronics. DOI:10.1049/cje.2016.05.022
552 Chinese Journal of Electronics 2016

Its main idea is to employ the block matrix to represent

II. Related Works the remainder matrix of the projection matrix. Its key
The fundamental quantity associated with CS system point is to find the coefficients matrix between the block
is the mutual coherence μ(D) parameter[5−8]. It can be matrix and the whole project matrix. Here, we present an
interpreted as the maximum absolute inner product be- efficient method to obtain it. Theoretically, if the block
tween two columns of the matrix D. An alternative def- matrix is optimal, then the whole projection matrix is
inition of μ(D) is the off-diagonal entry of Gram matrix optimal. In other words, the mutual coherence between
G with the largest magnitude, where G = D T D, each the whole projection matrix and the whole basis matrix
column of D was normalized[9]. is equal to the mutual coherence between the block matrix
The random Gaussian projection matrix Φ leads to a and blocked basis matrix.
sensing matrix in many earlier works. It obeys the RIP Assume that an optimized block matrix Φb ∈ RM×M
with high probability in theoretical analysis. However, op- was obtained. Φb is a sub-matrix of Φ. Suppose there is a
timization of the random Gaussian matrix might decrease coefficients matrix λ ∈ RM×(N −M) , which can represent
mutual coherence and enhance the quality of the recon- the remainder block of Φ by Φb λ, then Φ can be divided
struction in CS[9−14] . In Ref.[9], Elad proposed an itera- into Φb and Φb λ blocks. That is:
tive algorithm to shrink the t-averaged mutual coherence Φ = [Φb , Φb λ] (1)
between Φ and Ψ , where Ψ is fixed. In Ref.[10], Duarte-
Carvajalino and Sapiro presented different methods to op- Similarly, Ψ can be divided into two blocks. That is:
timize the projection matrix. They took the advantage of Ψ = [ΨA , ΨB ]T (2)
an eigenvalue decomposition process followed by a KSVD-
where ΨA ∈ RM×P , and ΨB ∈ R(N −M)×P . Because D is
based method, and made the Gram matrix as close as pos-
the product of Φ and Ψ then we obtain:
sible to the identity matrix. Based on Duarte’s work, Li
et al. proposed another method to design the projection D = ΦΨ = [Φb , Φb λ][ΨA , ΨB ]T = Φb ΨA + Φb λΨB (3)
matrix[11] . It focused on finding the “best” solution of the Let G = D T D, then:
optimal problem min  In −Ψ T ΦT ΦΨ 2F . An analyt-
Φ∈RM ×N
G =ΨAT ΦT T T
b Φb ΨA + ΨA Φb Φb λΨB
ical solution was derived in closed-form for optimizing pro- (4)
jection matrix. It also revealed that the solution has de- + ΨBT λT ΦT T T T
b Φb ΨA + ΨB λ Φb Φb λΨB
grees of freedom. Furthermore, it minimized the coherence Set X = Φb λΨB , Eq.(4) then becomes:
between the atoms of the equivalent dictionary among the
solution set. In Ref.[12], Xu et al. took the Equiangular G = ΨAT ΦT T T T T
b Φb ΨA + ΨA Φb X + X Φb ΨA + X X (5)

tight frame (ETF) into consideration and proposed an ap- One can see that ΨAT ΦT
b Φb ΨA is a kind of Gram matrix
proach to optimize the projection matrix. Although aver- with Φb and ΨA . Because ΨA is fixed and known and Φb is
age performances are improved, the optimized projection optimal, the mutual coherence of μ(Φb ΨA ) is a minimum
matrices are iteratively computed in these approaches. In and constant. Based on the definition of mutual coher-
Ref.[13], Zhang et al. presented a low-rank model to bring ence, to minimize μ(D) is to minimize the off-diagonal
the low rank Gram matrix to be near an ETF for the entry of G in Eq.(5). Hence, the best result is that the
projection design. This method guarantees both nearness sum of ΨAT ΦT T T
b X, X Φb ΨA and X X equals to 0. That
and low-rank properties. It overcomes the shortcoming is:
of Elad’s and Xu’s methods which do not guarantee the ΨAT ΦT T
b X + X Φb ΨA + X X = 0
T
(6)
new low-rank Gram matrix to be the nearest one to ETF Set U = Φb ΨA , Eq.(6) can be transferred into Eq.(7).
by shrinkage. Furthermore, a first-order algorithm[14] was
U TX + X TU + X TX = 0 (7)
deployed to obtain the nearest low rank correlation ma-
trix. However, it has high computational complexity. In Before we solve Eq.(7), we introduce Theorem 1.
Ref.[15], Cleju proposed an improved method via rank- Theorem 1 For the nonlinear matrix equation
constrained nearest correlation matrix to optimize pro- U T X + X T U + X T X = 0, given U ∈ RM×P , M < P
jection. What’s more, he pointed out that reducing the then the solution of X is
mutual coherence alone is not enough to obtain the opti-  
Λr 0
mal projection matrix. X= QT − U (8)
0 0 M×P
III. Block-Based Projection Matrix
where√Λr = diag(σ1 , σ2 , · · · , σr ), σ1 ≥ σ2 ≥ · · · ≥ σr ,
Design
σi = λi , λi is the eigenvalue of U T U ; the columns of Q
In order to minimize the mutual coherence, we pro- are orthonormal eigenvector of U T U .
pose a block-based method for projection matrix design. The Appendix A gives a brief proof.
 Block-Based Projection Matrix Design for Compressed Sensing 553

Eq.(8) is the solution of X in the Eq.(7). Substituting and the fixed threshold t = 0.2. Firstly, we study the abso-
Eq.(8) into X = Φb λΨB , we obtain: lute value of the element distribution in the Gram matrix
  (using Φ30×200 , Ψ200×400 ). Secondly, demonstration of the
Λr 0 relative error with different measurements (using Φm×80 ,
Φb λΨB = QT − U (9)
0 0 M×P Ψ80×120 , the cardinality T = 4) is [Link], we
By solving Eq.(9), we obtain the solution of λ. That explain the effect by using different cardinality (using
Φ25×80 , Ψ80×120 ).
is:
   Fig.1 is the absolute off-diagonal entries of Gram ma-
Λr 0 trix. In other words, it is the mutual coherence of the pro-
λ= Φ−1
b
T
Q − U ΨBT (ΨB ΨBT )−1
0 0 M×P jection matrix. It was obtained by using a fixed sparsifying
(10) matrix for four different projection matrices. It is known
Once λ is obtained, Φ can be easily computed as that a projection matrix with small off-diagonal entries
the relationship of Φ = [Φb , Φb λ]. For U T X + X T U + indicates that it has high reconstruction performance. It
X T X = 0, the Eq.(5) can be rewritten as: shows that the methods of Elad, Duarte and Xu optimize
the projection matrix when compared to the Gaussian
G = ΨAT ΦT
b Φb ΨA (11) matrix. However, the attenuations of these methods are
Obviously, the mutual coherence between Φ and Ψ relatively slow which does not contribute to enhancing the
equals to the mutual coherence between Φb and ΨA . that accuracy of the signal reconstruction. On the contrary,
is: the block-based optimal method proposed in this paper
μ(ΦΨ ) = μ(Φb ΨA ) (12) increases the attenuation of the off-diagonal elements.

For Φb is an optimized block matrix, μ(Φb ΨA ) is a

minimum. Hence, μ(ΦΨ ) is a minimum as well.
In summary, the main steps of the proposed method
for optimizing the projection matrix are depicted in Al-
gorithm 1 (using the notation defined above).

Algorithm 1 Algorithm of block-based optimal method

1: Obtain the optimized block projection matrix Φb ;
2: Divide basis matrix Ψ into blocks, that is Ψ = [ΨA , ΨB ]T ;
3: Decompose Φb ΨA by singular! value decomposition;
" #
−1 Λ r 0 T
4: Obtain λ by Φb Q −U ΨBT (ΨB ΨBT )−1 ;
0 0
M ×P
5: Obtain the projection matrix Φ by Φb and λ, that is
Φ = [Φb , Φb λ];
6: Update the projection matrix Φ by singular value decom-
position method.

As for the computational complexity of Algorithm 1,

it mainly depends on the complexity of Step 4. Compared
with the operation of multiplication, the inverse transform
is more time-consuming. The computational complexity
of the inverse transform of Φb and (ΨB ΨBT ) is O(M 3 ) and Fig. 1. Histogram of the absolute off-diagonal entries of Gram
O((N − M )3 ), respectively. Therefore, the computational matrix before and after optimization
complexity of the proposed algorithm is approximately
O(N 3 ). In Fig.2 we consider the performance of relative errors
using different methods for varying numbers of measure-
IV. Simulation and Results ments. The relative errors is defined as the relative num-
ber of errors and is a kind of recovery errors rate. The
In this section, we evaluate the performance of the pro- reconstruction algorithms are Orthogonal matching pur-
posed method. The parameters of basis matrix Ψ , mea- suit (OMP)[16] and Basis pursuit (BP)[17] . The original K
surement matrix Φ are similar to those in Ref.[9]. The sparse signal in Fig.2 is obtained, where the K nonzero
total number of sparse signals Tatol = 10000 and the it- coefficients are set by i.i.d. N (0, 1) and the remaining
erations iter = 1000. The individual parameters used in coefficients of x are set by 0. In order to eliminate the
Elad’s method were: the shrinkage parameter γ = 0.95 randomness in the experiment, the results are the aver-
554 Chinese Journal of Electronics 2016

age of 10000 synthetic signals in this paper. ment is much larger with OMP than that with BP.
Fig.2 shows that relative errors of OMP and BP de-
crease as m increases. As expected, all the optimization
methods improved the performance of CS. It is obvi-
ous that the block-based optimal method obtains bet-
ter reconstruction performance compared to other meth-
ods. Comparing Fig.2(a) with Fig.2(b), BP outperforms
OMP. Fig.2 indicates that for m=30, the performance of
the proposed method is improved compared to the non-
optimized method and Elad’s, Duarte-Carvajalino’s and
Xu’s method by 90:1, 29:1, 3.2:1 and 1.3:1 (the ratio is a
proportion between the relative number of errors of com-
pared methods and that of the proposed method) with
OMP reconstruction and 19:1, 10:1, 3:1 and 2:1 with BP
reconstruction, respectively.

Fig. 3. Relative errors as a function of the signals’ cardinal-

ity T . (a) Using OMP reconstruction; (b) Using BP
reconstruction

V. Conclusions
The projection matrix plays an important role in com-
pressed sensing. Its optimization has attracted widely con-
cerns recently. In this paper, a block-based method for
the design of the projection matrix is proposed. Experi-
mental results show that the block-based method is im-
proved significantly compared with the above-mentioned
optimization methods. In addition, the performance of the
proposed method is significant with using BP for vary-
ing number of measurements, and using OMP for varying
Fig. 2. Relative errors as a function of the number of measure- number of cardinality.
ments m. (a) Using OMP reconstruction; (b) Using BP
reconstruction
Appendix A
Theorem 1 For the nonlinear matrix equation U T X +
In Fig.3 we discuss relative errors using different op- X U + X T X = 0, given U ∈ RM ×P , M < P then the solu-
T

timization methods, with both OMP and BP for varying tion of X is

" #
numbers of cardinality,that is m(m = 25) is fixed and T Λr 0
X= QT − U (A-1)
is variable. Fig.3(a) and Fig.3(b) show that the relative 0 0
M ×P
errors of BP and OMP increase as T increases. The reason √
where Λr = diag(σ1 , σ2 , · · · σr ), σ1 ≥ σ2 ≥ · · · ≥ σr , σi = λi ,
is that as T increases, more measurements are needed to
λi is the eigenvalue of U T U ; the columns of Q are orthonormal
achieve the same performance. Also, as expected, for T =4, eigenvector of U T U .
the performance of the proposed method is improved com- Proof The Singular value decomposition (SVD) of UM ×P
pared to the non-optimized method and the method of is
Elad, Duarte-Carvajalino and Xu by 27:1, 23:1, 3:1 and " #
1.7:1 with OMP reconstruction and 3.5:1, 3.2:1, 1.9:1 and Λr 0
U = PM ×M QT P ×P (A-2)
1.4:1 with BP reconstruction, respectively. The improve- 0 0
M ×P
 Block-Based Projection Matrix Design for Compressed Sensing 555
√
where Λr = diag(σ1 , σ2 , · · · σr ), σ1 ≥ σ2 ≥ · · · ≥ σr , σi = λi , [8] V. Abolghasemi, S. Ferdowsi and S. Sanei, “A gradient-based
λi is the eigenvalue of U T U ; the columns of PM ×M are or- alternating minimization approach for optimization of the mea-
thonormal eigenvector of U U T ; the columns of QP ×P are or- surement matrix in compressive sensing”, Signal Processing,
Vol.92, No.4, pp.999–1009, 2012.
thonormal eigenvector of U T U .
[9] M. Elad, “Optimized projections for compressed sensing”, IEEE
Because P T P = I, then we have: Transactions on Signal Processing, Vol.55, No.12, pp.5695–
" #T " # 5702, 2007.
T Λr 0 Λr 0 [10] J.M. Duarte-Carvajalino and G Sapiro, “Learning to sense
U U =Q QT (A-3)
0 0 0 0 sparse signals: Simultaneous sensing matrix and sparsifying dic-
tionary optimization”, IEEE Transactions on Image Process-
In order to find the solution of X in the equation of ing, Vol.18, No.7, pp.1395–1408, 2009.
[11] G. Li, Z.H. Zhu, D.H. Yang, et al., “On projection matrix opti-
U T X + X T U + X T X = 0, we add U T U to the two sides
mization for compressive sensing systems”, IEEE Transactions
of the equation, then the equation transfers into as follows: on Signal Processing, Vol.61, No.11, pp.2887–2898, 2013.
[12] J.P. Xu, Y.M. Pi and Z.J. Cao, “Optimized projection matrix
U TU + U TX + X TU + X TX = U TU (A-4) for compressive sensing”, EURASIP Journal of Advance Signal
Process, Vol.2010, No.43, pp.1–8, 2010.
Obviously, [13] Q.H. Zhang, Y.L. Fu, H.F. Li, et al., “Optimized projection
matrix for compressed sensing”, Circuits, Systems, and Signal
U T U + U T X + X T U + X T X = (U + X )T (U + X ) (A-5) Processing, Vol.33, No.5, pp.1627–1636, 2014.
[14] Z.W. Wen and W.T. Yin, “A feasible method for optimization
Substituting Eqs.(A-3) and (A-5) into to Eq.(A-4), we ob- with orthogonality constraints”, Mathematical Programming,
tain: Vol.142, No.1–2, pp.397–434, 2013.
[15] N. Cleju, “Optimized projections for compressed sensing via
" #T " #
rank-constrained nearest correlation matrix”, Applied and
T Λr 0 Λr 0
(U +X ) (U +X ) = Q QT (A-6) Computational Harmonic Analysis, Vol.36, No.3, pp.495–507,
0 0 0 0 2014.
[16] J.A. Tropp and A.C. Gilbert, “Signal recovery from random
So " # measurements via orthogonal matching pursuit”, IEEE Trans-
Λr 0 actions on Infomation Theory, Vol.53, No.12, pp.4655–4666.
(U + X ) = QT (A-7)
0 0 2007.
[17] S.S. Chen, D.L. Donoho and M.A. Saunders, “Atomic decom-
That is: " # position by basis pursuit”, SIAM Journal on Scientific Com-
Λr 0 puting, Vol.20, No.1, pp.33–61, 1998.
X= QT − U (A-8)
0 0 LI Zhetao is an associate professor
and master supervisor in Xiangtan Uni-
versity. His main research interests in-
clude wireless network and compressive
References sensing.(Email: liztchina@[Link])
[1] E.J. Candes and M.B. Wakin, “An introduction to compres-
sive sampling”, IEEE Signal Process Magazine, Vol.25, No.2,
pp.21–30, 2008.
[2] Z.T. Li, J.X. Xie, D.B. Tu, et al., “Sparse signal recovery by
stepwise subspace pursuit in compressed sensing”, International XIE Jingxiong is a graduate in Xi-
Journal of Distributed Sensor Networks. Vol.2013, Article ID angtan University. His main research inter-
798537, 5 pages, 2013. ests include compressive sensing and signal
[3] L.C. Jiao, S. Yang, F. Liu, et al., “Development and prospect processing.
of compressive sensing”, Acta Electronica Sinica, Vol.39, No.1,
pp.18–22, 2011. (in Chinese)
[4] E.J. Candes, “The restricted isometry property and its implica-
tions for compressed sensing”, Comptes Rendus Mathematique,
Vol.346, No.9, pp.589–592, 2008.
[5] G.M. Shi, D.H. Liu and D.H. Gao, “Advances in theory and
application of compressed sensing”, Acta Electronica Sinica, ZHU Gengming (corresponding
Vol.37, No.5, pp.1070–1081, 2009. (in Chinese) author) is a professor in Hunan University
[6] Y.H. Rong, Zh. Cheng, D.D. Wei, et al., “The theory of com- of Science and Technology. His research
pressed sensing and reconstruction algorithm”, Acta Electronica interests include wireless sensor network
Sinica, Vol.39, No.1, pp.142–148, 2011. (in Chinese) and compressive sensing. (Email: geng-
[7] Z.T. Li, T. Pan, G.M. Zhu, et al., “A construction algorithm mingzhu@[Link])
of measurement matrix with low power average column coher-
ence”, Chinese Journal of Electronics, Vol.42, No.7, pp.1360–
1364, 2014. (in Chinese)