Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An x in $\mathbb{R}^n$ is said to be sparse if many of it's coefficients are zeroes. x is said to be compressible(approximately sparse) if many of its coefficients are close to zero.ie Let $x=(x_1,x_2,....x_n)$. Sort the absolute values of the coefficients in decreasing order with new indices as $|x_{(1)}|\geq|x_{(2)}|\geq,..,|x_{(n)}|$. x is said to be compressible if $|x_{(k)}|\leq C k^{-r},r>0$ for all $k=1,2,..,n$ where $C$ is a fixed constant. Coefficients $x_k$ don't follow any probability distribution.

My questions:

1) With this definition, every $x\in\mathbb{R}^n$ satisfies this power law as I can always find a constant(because I have only finite values) $C$ such that above power law is satisfied. But this shouldn't be the case because not every $x$ in $\mathbb{R}^n$ is compressible.

2)How do I choose $C$ so that this definition makes sense?

3) Is this definition even right? What am I missing?

share|improve this question
Are you sure the term compressible wasn't defined for infinite sequences? –  dls Mar 19 '12 at 20:40
You probably should know more about the $x$'s to make it right. Are they a result of some measurement/calculation? –  yohBS Mar 19 '12 at 20:47
@ dls- yes, It is defined for finite dimensional signal. It may be defined for infinite dimensional but in my case it is for finite set of values. –  Maan Mar 19 '12 at 22:52
@yohBS: So you are saying that this definition is wrong as it is written. x is just an n dimensional vector. It can represent the coefficient of some vector when written in some basis. –  Maan Mar 19 '12 at 22:56
Then maybe the definition is related to the thing that creates the signal. For a specific, given $n$-dimensional vector it is clearly meaningless. But maybe it makes sense for a family of signals. For example - sampling the electric field at given distances from a point charge, where the position, magnitude of the charge and direction of sampling varies, but you know that after sampling enough points it will decay as a power law. I'm just guessing here. –  yohBS Mar 19 '12 at 23:02
show 3 more comments

2 Answers

The definition looks just like the rule for determining convergent series. Using the ratio test, you can tell if a sequence of roots converges. As I recall, $\frac{1}{x}$ doesn't converge to zero. Rational values of $r$ don't converge quickly, $\frac{1}{\sqrt{x}}$, I wouldn't bet any money that's a sparse system. Are you sure $r > 0$ and not $r > 1$ ?

I should have made this a comment, sorry...

share|improve this answer
add comment

Definition is correct. $C$ is defined for any vector $x$, so you can't first choose $x$ and after that C. You can say that $x$ is $C,r$-compressible (or not) for fixed $C$ and $r$.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.