Compressing Data by Shortest Path Methods

Storage and transmission of signals tend to be resource demanding when the data are processed in their original size. This is not confined to multi-dimensional signals such as images, but is also most relevant in the one-dimensional case considered in this work. Compressing the data in such a way that close reconstructions can be found, is therefore a highly respected problem in signal processing.This paper demonstrates how a graph theory approach can yield optimal subsets by which all the original signal samples are to be represented. Under the restriction of bounded subset cardinality, the actual method guarantees to give an approximation with minimum distance from original data. Recognizing the problem as a constrained shortest path problem, enables us to derive simple algorithms which produce the exact solution in polynomial time.Closeness between original data and algorithm output is measured by any vector norm. The norm in question is applied to the difference between the original data vector and the unique reconstruction based on algorithm output. We consider the infinity and Euclidean norms, and present a complexity analysis of an algorithm incorporating both error measures.