检索结果-内蒙古大学图书馆

Locality-Sensitive Hashing for Chi2 Distance

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2012年第2期34卷 402-409页

作者： Gorisse, David Cord, Matthieu Precioso, Frederic Yakaz Lab F-75002 Paris France UPMC Sorbonne Univ LIP6 F-75005 Paris France CNRS Lab Informat Signaux & Syst Sophia Antipolis UNS I3S UMR6070 Sophia Antipolis 6903 France

In the past 10 years, new powerful algorithms based on efficient data structures have been proposed to solve the problem of Nearest Neighbors search (or Approximate Nearest Neighbors search). If the Euclidean Locality Sensitive Hashing algorithm, which provides approximate nearest neighbors in a euclidean space with sublinear complexity, is probably the most popular, the euclidean metric does not always provide as accurate and as relevant results when considering similarity measure as the Earth-Mover Distance and chi(2) distances. In this paper, we present a new LSH scheme adapted to chi(2) distance for approximate nearest neighbors search in high-dimensional spaces. We define the specific hashing functions, we prove their local-sensitivity, and compare, through experiments, our method with the Euclidean Locality Sensitive Hashing algorithm in the context of image retrieval on real image databases. The results prove the relevance of such a new LSH scheme either providing far better accuracy in the context of image retrieval than euclidean scheme for an equivalent speed, or providing an equivalent accuracy but with a high gain in terms of processing speed.

关键词： sublinear algorithm approximate nearest neighbors locality sensitive hashing chi2 distance image retrieval

来源：评论

学校读者我要写书评

暂无评论

Maximizing the overlap of two planar convex sets under rigid motions

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第1期37卷 3-15页

作者： Ahn, Hee-Kap Cheong, Otfried Park, Chong-Dae Shin, Chan-Su Vigneron, Antoine Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea Sejong Univ Dept Comp Sci & Engn Seoul South Korea Hankuk Univ Foreign Studies Sch Elect & Inform Engn Yongin South Korea INRA Unite Math & Informat Appl Jouy En Josas France

Given two compact convex sets P and Q in the plane, we compute an image of P under a rigid motion that approximately maximizes the overlap with Q. More precisely, for any epsilon > 0, we compute a rigid motion such that the area of overlap is at least 1-epsilon times the maximum possible overlap. Our algorithm uses O(1/epsilon) extreme point and line intersection queries on P and Q, plus O((1/epsilon(2)) log(1/epsilon)) running time. If only translations are allowed, the extra running time reduces to O((1/epsilon) log(1/epsilon)). If P and Q are convex polygons with n vertices in total that are given in an array or balanced tree, the total running time is O((1/epsilon) log n + (1/epsilon(2)) log(1/epsilon)) for rigid motions and O((1/epsilon) log n + (1/epsilon) log(1/epsilon)) for translations. (c) 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm sublinear algorithm convex shape geometric pattern matching

来源：评论

学校读者我要写书评

暂无评论

Deterministic Sparse sublinear FFT with Improved Numerical Stability

引用

RESULTS IN MATHEMATICS 2021年第2期76卷 53-53页

作者： Plonka, Gerlind von Wulffen, Therese Univ Gottingen Inst Numer & Appl Math Lotzestr 16-18 D-37083 Gottingen Germany

In this paper we extend the deterministic sublinear FFT algorithm in Plonka et al. (Numer algorithms 78:133-159, 2018. https://***/10.1007/s11075-017-0370-5) for fast reconstruction of M-sparse vectors x of length N = 2(J), where we assume that all components of the discrete Fourier transform (x) over cap = F(N)x are available. The sparsity of x needs not to be known a priori, but is determined by the algorithm. If the sparsity M is larger than 2(J/2), then the algorithm turns into a usual FFT algorithm with runtime O(N log N). For M-2 < N, the runtime of the algorithm is O(M-2 log N). The proposed modifications of the approach in Plonka et al. (2018) lead to a significant improvement of the condition numbers of the Vandermonde matrices which are employed in the iterative reconstruction. Our numerical experiments show that our modification has a huge impact on the stability of the algorithm. While the algorithm in Plonka et al. (2018) starts to be unreliable for M > 20 because of numerical instabilities, the modified algorithm is still numerically stable for M = 200.

关键词： Sparse FFT discrete Fourier transform sublinear algorithm Vandermonde matrices

来源：评论

学校读者我要写书评

暂无评论

Deterministic Metric 1-median Selection with a 1-o(1) Fraction of Points Ignored 27th

Deterministic Metric 1-median Selection with a 1-o(1) Fracti...

引用

27th International Computing and Combinatorics Conference (COCOON)

作者： Chang, Ching-Lueh Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan

ISBN: (纸本)9783030895433;9783030895426

Given an n-point metric space (M, d), metric 1-median asks for a point p is an element of M minimizing Sigma(x is an element of M) d(p, x). We show that for each computable function f : Z(+) -> Z(+) satisfying f(n) = omega(1), metric 1-median has a deterministic, o(n)-query, o(f(n) . log n)-approximation and nonadaptive algorithm. Previously, no deterministic o(n)-query o(n)approximation algorithms are known for metric 1-median.

关键词： Median selection 1-median problem Metric space sublinear algorithm Query complexity

来源：评论

学校读者我要写书评

暂无评论

Stronger L2/L2 Compressed Sensing;Without Iterating 2019

Stronger L2/L2 Compressed Sensing;Without Iterating

引用

51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Nakos, Vasileios Song, Zhao Harvard Univ Cambridge MA 02138 USA UT Austin Austin TX USA

ISBN: (纸本)9781450367059

We consider the extensively studied problem of l(2)/l(2) compressed sensing. The main contribution of our work is an improvement over [Gilbert, Li, Porat and Strauss, STOC 2010] with faster decoding time and significantly smaller column sparsity, answering two open questions of the aforementioned work. Previous work on sublinear-time compressed sensing employed an iterative procedure, recovering the heavy coordinates in phases. We completely depart from that framework, and give the first sublinear-time l(2)/l(2) scheme which achieves the optimal number of measurements without iterating;this new approach is the key step to our progress. Towards that, we satisfy the l(2)/l(2) guarantee by exploiting the heaviness of coordinates in a way that was not exploited in previous work. Via our techniques we obtain improved results for various sparse recovery tasks, and indicate possible further applications to problems in the field, to which the aforementioned iterative procedure creates significant obstructions.

关键词： compressed sensing sparse recovery sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient CUR Matrix Decomposition via Relative-Error Double-Sided Least Squares Solving 32

Efficient CUR Matrix Decomposition via Relative-Error Double...

引用

32nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI)

作者： Luan, Qi Zhao, Liang CUNY Grad Ctr PhD Program Math New York NY 10010 USA CUNY Lehman Coll Dept Comp Sci New York NY USA

ISBN: (纸本)9781728192284

Matrix CUR decomposition aims at representing a large matrix A with the product C . U . R, where C (resp. R) consists of a small collection of the original columns (resp. rows), and U is a small intermediate matrix connecting C and R. While modern randomized CUR algorithms have provided many efficient methods of choosing representative columns and rows, there hasn't been a method to find the optimal U matrix. In this paper, we present a sublinear-time randomized method to find good choices of the U matrix. Our proposed algorithm treats the task of finding U as a double-sided least squares problem min(Z) parallel to A - CZR parallel to(F), and is able to guarantee a close-to-optimal solution by solving a down-sampled problem of much smaller size. We provide worst-case analysis on its approximation error relative to theoretical optimal low-rank approximation error, and we demonstrate empirically how this method can improve the approximation of several large-scale real data matrices with a small number of additional computations.

关键词： Matrix Decomposition sublinear algorithm Stochastic algorithm CUR Decomposition

来源：评论

学校读者我要写书评

暂无评论

Moments, Random Walks, and Limits for Spectrum Approximation 36

Moments, Random Walks, and Limits for Spectrum Approximation

引用

36th Annual Conference on Learning Theory (COLT)

作者： Jin, Yujia Musco, Christopher Sidford, Aaron Singh, Apoorv Vikram Stanford Univ Stanford CA 94305 USA NYU New York NY 10003 USA

We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on [-1, 1] that cannot be approximated to accuracy e in Wasserstein-1 distance even if we know all of their moments to multiplicative accuracy (1 +/- 2(-Omega(1/epsilon)));this result matches an upper bound of Kong and Valiant [Annals of Statistics, 2017]. To obtain our result, we provide a hard instance involving distributions induced by the eigenvalue spectra of carefully constructed graph adjacency matrices. Efficiently approximating such spectra in Wasserstein-1 distance is a well-studied algorithmic problem, and a recent result of Cohen-Steiner et al. [KDD 2018] gives a method based on accurately approximating spectral moments using 2(Omega(1/epsilon)) random walks initiated at uniformly random nodes in the graph. As a strengthening of our main result, we show that improving the dependence on 1/epsilon in this result would require a new algorithmic approach. Specifically, no algorithm can compute an e-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability, even when given the transcript of 2(Omega(1/epsilon)) random walks of length 2(Omega(1/epsilon)) started at random nodes.

关键词： spectral density estimation moment methods random walks sublinear algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximizing the overlap of two planar convex sets under rigid motions

Maximizing the overlap of two planar convex sets under rigid...

引用

21st Annual Symposium on Computational Geometry

关键词： approximation algorithm sublinear algorithm convex shape geometric pattern matching

来源：评论

学校读者我要写书评

暂无评论

Rake, Peel, Sketch: The Signal Processing Pipeline Revisited

Rake, Peel, Sketch: The Signal Processing Pipeline Revisited

引用

作者： Robin SCHEIBLER ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE

学位级别：博士

The prototypical signal processing pipeline can be divided into four blocks. Representation of the signal in a basis suitable for processing. Enhancement of the meaningful part of the signal and noise reduction. Estimation of important statistical properties of the signal. Adaptive processing to track and adapt to changes in the signal statistics. This thesis revisits each of these blocks and proposes new algorithms, borrowing ideas from information theory, theoretical computer science, or communications. First, we revisit the Walsh-Hadamard transform (WHT) for the case of a signal sparse in the transformed domain, namely that has only K ≤ N non-zero coefficients. We show that an efficient algorithm exists that can compute these coefficients in O(K log 2 (K) log 2 (N/K)) and using only O(K log 2 (N/K)) samples. This algorithm relies on a fast hashing procedure that computes small linear combinations of transformed domain coefficients. A bipartite graph is formed with linear combinations on one side, and non-zero coefficients on the other. A peeling decoder is then used to recover the non-zero coefficients one by one. A detailed analysis of the algorithm based on error correcting codes over the binary erasure channel is given. The second chapter is about beamforming. Inspired by the rake receiver from wireless com- munications, we recognize that echoes in a room are an important source of extra signal diversity. We extend several classic beamforming algorithms to take advantage of echoes and also propose new optimal formulations. We explore formulations both in time and frequency domains. We show theoretically and in numerical simulations that the signal-to-interference-and-noise ratio increases proportionally to the number of echoes used. Finally, beyond objective measures, we show that echoes also directly improve speech intelligibility as measured by the perceptual evaluation of speech quality (PESQ) metric. Next, we attack the problem of direction of arrival of a

关键词： Walsh-Hadamard transform sparsity sublinear algorithm peeling decoder beamforming rake receiver echoes perceptual evaluation of speech quality (PESQ) direction of arrival finite rate of innovation wideband high resolution adaptive filter recursive least squares least squares sketching conjugate gradient room impulse response generation Python hardware microphone arrays reproducible research

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：