Is uniqueness important?
We’ve been trying to find rank one sign matrix decompositions for arbitrary matrices: 
where 
are sign matrices of conformal dimensions, and 
is diagonal.
Pretty much, my advisor seems be aiming for any such sign decomposition, but I’m uncomfortable with that. Experimentally, I’ve constructed matrices as sums of 10 randomly weighted sign matrices, and found that just taking any decomposition (I used basis pursuit to find one) can give you about half as many possible rank one matrices having nonzero coefficients. So, if 
was 
with 
, you might get 
out of 
rank one matrices contributing to . (I counted 
, 
, 
, and 
as the same matrix, so there are 
unique rank one sign matrices in my dictionary).
This says two things to me: 1) we need to somehow be choosy about the decomposition we aim for, to ensure it has nice properties in some sense, even if it doesn’t give the holy grail of sparse representation, and 2) in this context, we shouldn’t think that representations whose 
coefficients are minimal are remotely similar to the sparse representations. The latter point is because the dictionary in this case (of rank one sign matrices) definitely doesn’t satisfy a RIP.
Possibly relevant posts:
- A dictionary, or not? (1/27/2010)
- A way not to get sign decompositions (2/26/2010)
- Another sign matrix problem (3/26/2010)