random


restricted isometry constants


























































































































































































































































































































































































































































































relaxed












Definition 2.1 
[15] For each integer 

, define the restricted
 isometry constant 
 of a matrix  to be the smallest number such that  holds for all 
-sparse vectors 
. A vector is said to be 
-sparse if it has at most 
 non-zero 
entries. The matrix 
 is said to satisfy the 
-restricted isometry property 
with restricted isometry 
constant . 































Theorem 2.1 [15] Assume that 
 and 
. Then the noisy CS solution 
(2.2) obeys: 
 
   with small constants 
 and 
 that are explicitly given in [15] and 
 denoting the best 
-sparse 
approximation of  by keeping the largest  entries of 
. 























atoms




overcomplete















































































noisy



relaxed


























lower-level
upper-level



















Sparse coding






Dictionary update














































































































































































































































































































































































learning curve









































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































multiple measurement vector












































































































































































































Theorem  6.1 (Chern
off bounding method).
For any random variable 
 and 

, the following inequalities hold:  



 (6.1) 
and  



 (6.2) 
conditioned on the fact that the right hand side exists.















































rate









































































































compensates











































































































































































CM for random-block measurement

Let  denote 
a subgaussian random variable with zero 
mean and unit variance and subgaussian norm . Let 
 be random matrices drawn independently, where each 
 is populated with i.i.d. 
realizations of the renor
malized random variable . Then, 



 (6.15) 
where  and  are absolute constants. 
 and 
 are defined below.  
 (6.16) 
 
 (6.17) 
where  represents the vector of block-wise energies. 




CM for repeated-block measurement

Let  be a 
random 
 matrix populated with i.i.d. 
Gaussian entries having variance , and let  be an 

 block-diagonal matrix as defined above and 
 for all 
. Then, for ,   



(6.18) where  and  are absolute constants. 
 and 
 are defined below.  
 (6.19) 
 
 (6.20) 
where  represents the vector of eigenvalues of 
when 
. 






















































































sketch
sketching







































Strong convexity









strong convexity












strong convexity for smooth functions





 




































Given that: 
1)  is an -strongly convex function of  2) For any outcome of , we have 
 with 
 the squared error is bounded as:   (6.28) 
Proof. 































































Suppose 
 for every 

 and 

. Assume that 
 and  are minimizers of  and  over . Then,   
 (6.31) 
Proof.  





























































































































ssuming 
 is the same for all 

, with probability 

 for 
,   (6.42) 
where 
. 











































































endmember variability
























































































































































































































































































































































































































































































































































































































































































IEEE Trans. on Information Theory

IEEE Trans. on Information Theory

Mathematical Surveys and 
Monographs 89, . American Mathematical Society


Transactions on Signal Processing


Transactions on Image Processing













Transactions on Signal Processing



Transactions on Signal Processing



Proc. Int. Conf. Acoustics, Speech and Signal 
Processing (ICASSP)






Compte Rendus de l™Academie des Sciences

Annals of Statistics




























IEEE International Conference on Image Processing (ICIP)








in Proceedings of IEEE Computer Vision and Pattern Recognition (CVPR)





Annual International Conference on Machine Learning
IEEE Transactions on Signal Processing