Subspaces clustering approach to lossy image compression

In this contribution lossy image compression based on sub- spaces clustering is considered. Given a PCA factorization of each cluster into subspaces and a maximal compression error, we show that the selec- tion of those subspaces that provide the optimal lossy image compression is equivalent to the 0-1 Knapsack Problem. We present a theoretical and an experimental comparison between accurate and approximate algo- rithms for solving the 0-1 Knapsack problem in the case of lossy image compression.