Problems in Sparse Approximation, On the Side

Given v in R^n, an orthonormal basis of vectors u_1,...,u_n, and an integer B << n, a sparse approximation problem is to find a linear combination v' of at most B of the basis vectors to minimize ||v-v'||_2. In this case, we can solve the problem optimally by picking the B largest | < v . u_i > |. A problem of my interest is the variation where we have some side information about v, or alternatively, additional constraints on v besides sparseness. For example, we may know that v is zero in at most t dimensions, or we may know the t dimensions in which it is zero, or we may know the norm of v projected on those dimensions where it exceeds certain threshold, etc. What is the complexity of such problems?