1
$\begingroup$

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?

  • 0
    I think YohBS has the right idea. Perhaps this is a case of engineers not making careful definitions (by the standards of pure math).2012-10-27

2 Answers 2

2

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$.

1

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...