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