000109426 001__ 109426
000109426 005__ 20190225185134.0
000109426 037__ $$aARTICLE
000109426 245__ $$aOn finding nearest neighbors in a set of compressible signals
000109426 269__ $$a2007
000109426 260__ $$c2007
000109426 336__ $$aJournal Articles
000109426 520__ $$aNumerous 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.
000109426 6531_ $$asparsity
000109426 6531_ $$aapproximate nearest neighbors
000109426 6531_ $$aLTS2
000109426 6531_ $$alts2
000109426 700__ $$0241006$$g114569$$aJost, Philippe
000109426 700__ $$0240428$$g120906$$aVandergheynst, Pierre
000109426 773__ $$tIEEE Trans. Sig. Process.
000109426 909C0 $$xU10380$$0252392$$pLTS2
000109426 909CO $$pSTI$$particle$$ooai:infoscience.tind.io:109426
000109426 937__ $$aEPFL-ARTICLE-109426
000109426 973__ $$rREVIEWED$$sSUBMITTED$$aEPFL
000109426 980__ $$aARTICLE