Minimizing image compression error (DCT)

Question

I'm doing an assignement on image compression.

I have to quantify the error given as $||A-\hat{A}||^2/||A||^2$, where $|\cdot|$ is the Eucledian norm.

I really need help, so please just give some advice.

Answer 1

You have to minimize $$\Big( \sum_{i \in \{m \times n\}} \|(A,\phi_i)\phi_i\| - \sum_{i \in I_N} \|(A,\phi_i)\phi_i\| \Big)\bigg/ \sum_{i \in \{m \times n\}} \|(A,\phi_i)\phi_i\|.$$

Discard the denominator because it is constant for the scope of your optimization. So is the leftmost sum. Then this is equal to maximizing $$\sum_{i \in I_N} \|(A,\phi_i)\phi_i\| = \sum_{i \in I_N} \|(A,\phi_i)\| \cdot \|\phi_i\| $$

And since your basis functions are normalized (part of being orthonormal) $\forall i \ : \ \|\phi_i\| = 1$. Thus, maximize

$$\sum_{i \in I_N} \|(A,\phi_i)\|$$

which is clearly achieved by picking those basis functions $\phi_i$ via set $I$ that result in the largest $\|(A,\phi_i)\|$ of a given image $A$.