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 x 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
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 ?
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.
No comments:
Post a Comment