Sparsity and Compressibility
By. Younghoon, Jung
26 Sep 2020

Vector의 sparsity와 compressibility는 어떻게 이야기해야 할까?

Notations

지금부터는 다음의 표현을 사용한다.

[N]={1,2,...,N}[N] = \{1,2,...,N\} card(S)=the cardinality of a set Scard(S) = \textrm{the cardinality of a set } S

Sparsity and Compressibility

먼저 벡터 x∈CNx\in\mathbb{C}^N의 support는 xx의 nonzero entries의 index set으로 정의한다:

supp(x):={j∈[N]∣xj≠0}.supp(x) := \{j\in[N] | x_j \neq 0\}.

그리고 벡터 x∈CNx\in\mathbb{C}^N가 아래의 조건을 만족하면 s-sparse 하다라고 정의한다.

∥x∥0:=card(supp(x))≤s.\| x \|_0 := card(supp(x)) \leq s.

즉, xx의 support의 크기가 s 이하면 xx는 s-sparse 하다.

Remark ∥⋅∥0\|\cdot\|_0은 편의상 l0l_0-norm이라고 불리는데 norm이나 quasinorm이 아니다. 그리고 다음과 같은 limiting property를 가진다.

∥x∥pp=∑j=1N∣xj∣p→∑j=1Nχ{xj≠0}=card({j∈[N]:xj≠0})  as  p→0.\|x\|_p^p = \sum_{j=1}^N |x_j|^p \rightarrow \sum_{j=1}^{N}\chi_{\{x_j\neq 0\}} = card(\{j\in[N]:x_j\neq 0\}) ~~\textrm{as}~~ p\rightarrow 0.

Sparsity는 너무 강한 조건이고 해석학적으로 다루기 힘들기 때문에 relaxation으로써 더 약한 조건인 Compressibility 개념이 필요하다.

ss-term approximation

먼저 벡터 xx의 compression을 최대 s개를 제외한 나머지 성분을 0으로 만드는 것으로 생각할 수 있다. 이렇게 얻어진 벡터를 s-term approximation of xx (s≪Ns \ll N)라고 부른다. 이 경우 벡터가 얼마나 잘 근사되었는 지를 다음과 같이 정의되는 error of best s-term approximation으로 측정할 수 있다.

For p>0p>0, the lpl_p-error of best s-term approximation to a vector x∈CNx\in\mathbb{C}^N is

σs(x)p:=inf⁡{∥x−z∥p, z∈CN is s-sparse}.\sigma_s(x)_p := \inf\{ \|x-z\|_p,~z\in\mathbb{C}^N~\textrm{is s-sparse} \}.

Remark 위의 infimum은 xx component 중에서 절대값이 가장 큰 s 개의 entries를 가지는 s-sparse 벡터 zz에 의해서 달성된다. 예를들어 x=(2,1,1,1)x=(2,1,1,1)일 때 2-sparse vector (2,1,0,0)(2,1,0,0)와 (2,0,1,0)(2,0,1,0)는 infimum을 만족한다. 즉, infimum은 pp값에 상관없이 달성 가능하지만 이를 만족하는 벡터가 유일하지는 않다.

방금 정의한 σs(x)p\sigma_s(x)_p를 이용하면 ss가 증가할 때 best s-term approximation이 빨리 감소하면 x∈CNx\in\mathbb{C}^N는 compressible 하다고 생각할 수 있다. 이 관점에서는 어떤 조건에서 best s-term approximation error가 빨리 감소하는지 생각해야 한다. 증명은 생략하고 다음의 Theorem을 살펴보자.

Theorem For any q>p>0q>p>0 and any x∈CNx\in\mathbb{C}^N the inequality

σs(x)q≤cp,qs1/p−1/q∥x∥p\sigma_s(x)_q \leq \frac{c_{p,q}}{s^{1/p - 1/q}} \|x\|_p

holds with

cp,q:=[(pq)p/q(1−pq)1−p/q]1/p≤1.c_{p,q}:=\left[ \left(\frac{p}{q}\right)^{p/q}\left(1-\frac{p}{q}\right)^{1-p/q} \right]^{1/p} \leq 1.

위 Theorem에 따르면 p>0p>0이면 error를 컨트롤 할 수 있고, p가 0에 가까울수록 error가 빠르게 줄어든다다. 예를 들어 (p,q)=(1,2)(p, q) = (1,2)라면 아래와 같다.

σs(x)2≤12s∥x∥1.\sigma_s(x)_2 \leq \frac{1}{2\sqrt{s}}\|x\|_1.

ss-significant components

compressibility를 이야기 하는 다른 방법으로 significant components의 수를 기준으로 삼을 수 있다. 즉, 다음의 값이 작으면 compressible 하다고 이야기한다.

card{j∈[N] ∣ ∣xj∣≥t}card\{j\in[N]~ |~ |x_j|\geq t\}

이 조건을 만족하는 벡터를 다루기 위해서 weak lpl_p-spaces를 도입한다.

Definition For p>0p>0, the weak lpl_p space wpNw_p^N is the space CN\mathbb{C}^N equipped with the quasinorm

∥x∥p,∞:=inf⁡{M≥0 ∣ card{j∈[N] ∣ ∣xj∣≥t}≤Mptp  for all  t>0}.(1)\tag{1} \| x \|_{p,\infty} := \inf \bigg\{ M\geq 0 ~|~ card\{j\in[N]~ |~ |x_j|\geq t\}\leq \frac{M^p}{t^p}~~\textrm{for all}~~t>0 \bigg\}.

여기서 (1)이 quasinorm이기 위해서 Non-negativity와 Absolute homogeneity는 쉽게 확인 가능하고 나머지 마지막 부등호 조건은 다음의 부등식으로 주어진다.

p>0p>0 이면

∥x1+⋯+xk∥p,∞≤kmax⁡{1,1/p}(∥x1∥p,∞+⋯+∥xk∥p,∞)\| x^1 + \cdots + x^k \|_{p,\infty} \leq k^{\max \{1,1/p\} }(\|x^1\|_{p,\infty}+\cdots+\|x^k\|_{p,\infty})

where x1,...,xk∈CNx^1,...,x^k\in\mathbb{C}^N.

(1)의 weak lpl_p-quasinorm을 좀 더 사용하기 쉬운 형태로 다시 표현할 수 있다.

p>0p>0 이면

∥x∥p,∞=max⁡k∈[N]k1/pxk∗\|x\|_{p,\infty} = \max_{k\in[N]} k^{1/p}x_k^*

where x∗∈R+Nx^*\in\mathbb{R}_+^N denote the nonincreasing rearrangement of x∈CNx\in\mathbb{C}^N.

새로운 표현을 이용하면 lpl_p-norm과 직접 비교 가능하고

∥x∥p,∞≤∥x∥p,\|x\|_{p,\infty}\leq\|x\|_p,

다음과 같이 error of best s-term approximation도 bound 할 수 있다.

Proposition For any q>p>0q>p>0 and x∈CNx\in\mathbb{C}^N, the inequality

σs(x)q≤dp,qs1/p−1/q∥x∥p,∞\sigma_s(x)_q \leq \frac{d_{p,q}}{s^{1/p-1/q}}\|x\|_{p,\infty}

holds with

dp,q:=(pq−p)1/q.d_{p,q}:=\left(\frac{p}{q-p}\right)^{1/q}.