On finding nearest neighbors in a set of compressible signals
Numerous applications demand that we manipulate large sets of very high-dimensional signals. A simple yet common example is the problem of finding those signals in a database that are closest to a query. In this paper, we tackle this problem by restricting our attention to a special class of signals that have a sparse approximation over a basis or a redundant dictionary. We take advantage of sparsity to approximate quickly the distance between the query and all elements of the database. In this way, we are able to prune recursively all elements that do not match the query, while providing bounds on the true distance. Validation of this technique on synthetic and real data sets confirms that it could be very well suited to process queries over large databases of compressed signals, avoiding most of the burden of decoding.
submitted_1col.pdf
openaccess
555.1 KB
Adobe PDF
02babfc414a028bdc2956f93815580e2
submitted_2cols.pdf
openaccess
565.08 KB
Adobe PDF
8f2df4c6bfba662e7c01272d7989432c