## Tuesday, July 03, 2012

### The Cost of Not Knowing

After editing this answer again, I wanted to put in perspective the cost of not knowing over time.

When solving for x in dimension N, you have to sample x N times. It's been known for a long time.

Your cost for discovering x yet not knowing anything about it is N

When solving for x in dimension N and knowing  it is K-sparse, you have to sample x CKlog(N/K) times if you don't know where the zeros are. It's been known since 2004.

With this knowledge, your cost for discovering x is now CKlog(N/K) most of the times

When solving for x of dimension N and knowing it is K-sparse, you have to sample x K+1 times if you don't know where the zeros are but have some knowledge of the distribution of the non-zeros elements and how to interrogate x:. It's been known since 2011.

With this knowledge, your cost for discovering x is now K+1 in specific instances

When solving for x in dimension N and knowing it is K-sparse, you have to sample x K times if you know where the zeros are. It's been known for a long time.

With this knowledge, your cost for discovering x is now K

( since Clog(N/K) is roughly 4 most of the time, not knowing where the zeros are will cost you roughly 4K-K = 3K see The answer is still No)

When solving for in dimension N, you have to sample  x a few times if you have some knowledge of the deeper inter-dependencies between the elements of x. It's been shown to work recently

With this knowledge,  your cost for discovering x can be pretty low.
How low ? we're not sure yet

The cost of not knowing probably costs you the implementation of a mind boggling technology or the discovery of a hidden gem.. What do you know ?

Related: The answer is still No

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.