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

Detection of Long Edges on a Computational Budget: A sublinear Approach

SIAM JOURNAL ON IMAGING SCIENCES 2015年第1期8卷 458-483页

作者： Horev, Inbal Nadler, Boaz Arias-Castro, Ery Galun, Meirav Basri, Ronen Weizmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel Univ Calif San Diego Dept Math La Jolla CA 92093 USA

Edge detection is a challenging, important task in image analysis. Various applications require real-time detection of long edges in large and noisy images, possibly under limited computational resources. While standard edge detection methods are computationally fast, they perform well only at low levels of noise. Modern sophisticated methods, in contrast, are robust to noise, but may be too slow for real-time processing of large images. This raises the following question, which is the focus of our paper: How well can one detect long edges in noisy images under severe computational constraints that allow only a fraction of all image pixels to be processed? We make several theoretical and practical contributions regarding this problem. We develop possibly the first sublinear algorithm to detect long straight edges in noisy images. In addition, we theoretically analyze the inevitable tradeoff between its detection performance and the allowed computational budget. Finally, we demonstrate its competitive performance on both simulated and real images.

关键词： edge detection sublinear algorithms group testing design of experiments

来源：评论

学校读者我要写书评

暂无评论

sublinear Time Eigenvalue Approximation via Random Sampling

引用

ALGORITHMICA 2024年第6期86卷 1764-1829页

作者： Bhattacharjee, Rajarshi Dexter, Gregory Drineas, Petros Musco, Cameron Ray, Archan Univ Massachusetts Manning Coll Informat & Comp Sci Amherst MA USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We study the problem of approximating the eigenspectrum of a symmetric matrix A is an element of R-nxn with bounded entries (i.e., parallel to A parallel to(infinity) <= 1). We present a simple sublinear time algorithm that approximates all eigenvalues of A up to additive error +/-epsilon n using those of a randomly sampled (O) over tilde (log(3)n/epsilon(3)) x (O) over tilde (log(3)n/epsilon(3)) principal submatrix. Our result can be viewed as a concentration bound on the complete eigenspectrum of a random submatrix, significantly extending known bounds on just the singular values (the magnitudes of the eigenvalues). We give improved error bounds of +/- epsilon root nnz(A) and +/- epsilon parallel to A parallel to(F) when the rows of A can be sampled with probabilities proportional to their sparsities or their squared l(2) norms respectively. Here nnz(A) is the number of non-zero entries in A and parallel to A parallel to(F) is its Frobenius norm. Even for the strictly easier problems of approximating the singular values or testing the existence of large negative eigenvalues (Bakshi, Chepurko, and Jayaram, FOCS '20), our results are the first that take advantage of non-uniform sampling to give improved error bounds. From a technical perspective, our results require several new eigenvalue concentration and perturbation bounds for matrices with bounded entries. Our non-uniform sampling bounds require a new algorithmic approach, which judiciously zeroes out entries of a randomly sampled submatrix to reduce variance, before computing the eigenvalues of that submatrix as estimates for those of A. We complement our theoretical results with numerical simulations, which demonstrate the effectiveness of our algorithms in practice.

关键词： Eigenvalue approximation sublinear algorithms Randomized algorithms Symmetric matrices

来源：评论

学校读者我要写书评

暂无评论

APPROXIMATELY COUNTING TRIANGLES IN sublinear TIME

引用

SIAM JOURNAL ON COMPUTING 2017年第5期46卷 1603-1646页

作者： Eden, Talya Levi, Amit Ron, Dana Seshadhri, C. Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada Univ Calif Santa Cruz Comp Sci Dept Santa Cruz CA 95064 USA

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex -pair queries, and neighbor queries. We show that for any given approximation parameter 0 < epsilon < 1, the algorithm provides an estimate (t) over cap such that, with high constant probability, (1 - epsilon) . t < <(t)over cap> < (1 + epsilon) . t, where t is the number s12triangles in the graph G. The expected query complexity of the algorithm is ((n)(t1/3) + min{m, (m3/2)(t) }) . poly(log n, 1/epsilon), where n is the number of vertices in the graph and m is the number of edges. The expected running time of the algorithm is (n/(t)1/3 + m(3/2)/t) . poly(log n,1/epsilon) We also prove that Omega(n/(t)1/3 + min{m, m(3/2)/t}) queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to the dependence on poly(log n, 1/epsilon).

关键词： triangles counting sublinear algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

ON APPROXIMATING THE NUMBER OF k-CLIQUES IN sublinear TIME

引用

SIAM JOURNAL ON COMPUTING 2020年第4期49卷 747-771页

作者： Eden, Talya Ron, Dana Seshadhri, C. MIT CSAIL Cambridge MA 02141 USA Tel Aviv Univ Dept Elect Engn IL-69978 Tel Aviv Israel Univ Calif Santa Cruz Santa Cruz CA 95064 USA

We study the problem of approximating the number of k-cliques in a graph when given query access to the graph. We consider the standard query model for general graphs via (1) degree queries, (2) neighbor queries, and (3) pair queries. Let n denote the number of vertices in the graph, m the number of edges, and C-k the number of k-cliques. We design an algorithm that outputs a (1+epsilon)-approximation (with high probability) for C-k, whose expected query complexity and running time are O(n/C-k(1/k) + m(k/2)/C-k)poly(logn, n, 1/epsilon, k). Hence, the complexity of the algorithm is sublinear in the size of the graph for C-k = omega(m(k/2-1)) Furthermore, we prove a lower bound showing that the query complexity of our algorithm is essentially optimal (up to the dependence on log n, 1/epsilon, and k). The previous results in this vein are by Feige [SIAM J. Comput., 35 (2006), pp. 964-984] and by Goldreich and Ron [Random Structures algorithms, 32 (2008), pp. 473-493] for edge counting (k = 2) and by Eden, Levi, Ron, and Seshadhri [SIAM T. Comput., 46 (2017), pp. 1603-1646] for triangle counting (k = 3). Our result matches the complexities of these results. The previous result by Eden et al. hinges on a certain amortization technique that works only for triangle counting and does not generalize for larger cliques. We obtain a general algorithm that works for any k >= 3 by designing a procedure that samples each k-clique incident to one of the vertices of a given set S of vertices with approximately equal probability.

关键词： sublinear algorithms counting cliques approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear TIME APPROXIMATION OF THE COST OF A METRIC k-NEAREST NEIGHBOR GRAPH

引用

SIAM JOURNAL ON COMPUTING 2024年第2期53卷 524-571页

作者： Czumaj, Artur Sohler, Christian Univ Warwick Dept Comp Sci Coventry CV4 7AL England Univ Warwick Ctr Discrete Math & its Applicat DIMAP Coventry CV4 7AL England Univ Cologne Dept Math & Comp Sci D-50923 Cologne Germany

Let (X, d) be an n -point metric space. We assume that (X, d) is given in the distance oracle model, that is, X = {1, ... , n} and for every pair of points x, y from X we can query their distance d(x, y) in constant time. A k -nearest neighbor (k -NN) graph for (X, d) is a directed graph G = (V, E) that has an edge to each of v's k nearest neighbors. We use cost(G) to denote the sum of edge weights of G. In this paper, we study the problem of approximating cost(G) in sublinear time when we are given oracle access to the metric space (X, d) that defines G. Our goal is to develop an algorithm that solves this problem faster than the time required to compute G. We first present an algorithm that in Owidetilde\\varepsilon(n2/k) time with probability at least 23 approximates cost(G) to within a factor of 1 + \varepsilon. Next, we present a more elaborate sublinear algorithm that in time Owidetilde \ \varepsilon(min{nk3/2,n2/k}) computes an estimate

关键词： sublinear algorithms approximation algorithm nearest neighbors

来源：评论

学校读者我要写书评

暂无评论

What's the Frequency, Kenneth?: sublinear Fourier Sampling Off the Grid

引用

ALGORITHMICA 2015年第2期73卷 261-288页

作者： Boufounos, Petros Cevher, Volkan Gilbert, Anna C. Li, Yi Strauss, Martin J. Mitsubishi Elect Res Labs Cambridge MA 02139 USA Ecole Polytech Fed Lausanne Lab Informat & Inference Syst CH-1015 Lausanne Switzerland Univ Michigan Dept Math Ann Arbor MI 48109 USA Max Planck Inst Informat Dept 1 D-66123 Saarbrucken Germany Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA

We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form;i.e., exponential polynomials with a noise term. The frequencies satisfy and for some . We design a sublinear time randomized algorithm which, for any , which takes samples of and runs in time proportional to number of samples, recovering and such that, with probability , the approximation error satisfies and for all with . We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.

关键词： Sparse signal recovery Fourier sampling sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Sampling-based sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning

引用

JOURNAL OF THE ACM 2022年第5期69卷 1–72页

作者： Chia, Nai-Hui Gilyen, Andras Pal Li, Tongyang Lin, Han-Hsuan Tang, Ewin Wang, Chunhao Univ Texas Austin Dept Comp Sci Austin TX 78712 USA Alfred Renyi Inst Math Realtanoda St 13-15 H-1053 Budapest Hungary CALTECH Inst Quantum Informat & Matter Pasadena CA 91125 USA Peking Univ Ctr Frontiers Comp Studies Sch Comp Sci Beijing Peoples R China MIT Ctr Theoret Phys 77 Massachusetts Ave Cambridge MA 02139 USA Univ Washington Seattle WA 98195 USA Penn State Univ Dept Comp Sci & Engn 207 Elect Engn West University Pk PA 16802 USA WM Rice Univ Dept Comp Sci 6100 Main St Houston TX 77005 USA Sch Comp Sci Ctr Frontiers Comp Studies 5 Yiheyuan Rd Beijing 100871 Peoples R China Natl Tsing Hua Univ Dept Comp Sci 101Kuang Fu RdSec 2 Hsinchu 300 Taiwan Paul G Allen Ctr 185 E Stevens Way NE Seattle WA 98195 USA

We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation systems [STOC'19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyen et al. [STOC'19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all prior results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: l(2)-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.

关键词： Quantum-inspired classical algorithms theoretical machine learning quantum computing sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

NOISE TOLERANCE OF EXPANDERS AND sublinear EXPANSION RECONSTRUCTION

引用

SIAM JOURNAL ON COMPUTING 2013年第1期42卷 305-323页

作者： Kale, Satyen Peres, Yuval Seshadhri, C. IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA Microsoft Res Redmond WA 98052 USA Sandia Natl Labs Livermore CA 94550 USA Princeton Univ Princeton NJ 08544 USA

We consider the problem of online sublinear expander reconstruction and its relation to random walks in "noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph G, we want to convert this graph into a bounded-degree expander G' changing G as little as possible. The graph G' will be output by a distributed filter: this is a sublinear time procedure that, given a query vertex, outputs all its neighbors in G' and can do so even in a distributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We also design sublinear time procedures to distinguish vertices of the expander part from those in the noise part and use this procedure in the reconstruction algorithm.

关键词： graph expansion random walks sublinear algorithms sublinear reconstruction

来源：评论

学校读者我要写书评

暂无评论

Interactive Proofs of Proximity: Delegating Computation in sublinear Time 13

Interactive Proofs of Proximity: Delegating Computation in S...

引用

45th Annual ACM Symposium on the Theory of Computing (STOC)

作者： Rothblum, Guy N. Vadhan, Salil Wigderson, Avi Microsoft Res Redmond WA USA Harvard Univ Ctr Res Computat & Soc Cambridge MA 02138 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Inst Adv Study Princeton NJ 08540 USA

ISBN: (纸本)9781450320290

We study interactive proofs with sublinear-time verifiers. These proof systems can be used to ensure approximate correctness for the results of computations delegated to an untrusted server. Following the literature on property testing, we seek proof systems where with high probability the verifier accepts every input in the language, and rejects every input that is far from the language. The verifier's query complexity (and computation complexity), as well as the communication, should all be sublinear. We call such a proof system an Interactive Proof of Proximity (IPP). " On the positive side, our main result is that all languages in NC have Interactive Proofs of Proximity with roughly \Fn query and communication and complexities, and polylog(n) communication rounds. This is achieved by identifying a natural language, membership in an affine subspace (for a structured class of subspaces), that is complete for constructing interactive proofs of proximity, and providing efficient protocols for it. In building an IPP for this complete language, we show a tradeoff between the query and communication complexity and the number of rounds. For example, we give a 2 -round protocol with roughly n3/4 queries and communication. " On the negative side, we show that there exist natural languages in NCI-, for which the sum of queries and communication in any constant-round interactive proof of proximity must be polynomially related to n. In particular, for any 2 -round protocol, the sum of queries and communication must be at least S2( \/7n). Finally, we construct much better IPPs for specific functions, such as bipartiteness on random or wellmixing graphs, and the majority function. The query complexities of these protocols are provably better (by exponential or polynomial factors) than what is possible in the standard property testing model, i.e. without a prover.

关键词： Interactive Proofs sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

sublinear approximation of signals

Sublinear approximation of signals

引用

Conference on Intelligent Integrated Microsystems

作者： Gilbert, Anna C. Strauss, Martin J. Tropp, Joel A. Vershynin, Roman Univ Michigan Dept Math Ann Arbor MI 48109 USA Univ Michigan Dept Elect Engn Ann Arbor MI 48109 USA Univ Calif Davis Dept Math Davis CA 95616 USA

ISBN: (纸本)0819462888

It has recently been observed that sparse and compressible signals call be sketched using very few nonadaptive linear measurements in comparison with the length of the signal. This sketch can be viewed as an embedding of an entire class of compressible signals into a low-dimensional space. In particular, d-dimensional signals with m nonzero entries (m-sparse signals) can be embedded in O(m log d) dimensions. To date, most algorithms for approximating or reconstructing the signal from the sketch, such as the linear programming approach proposed by Candes-Tao and Donoho, require time polynomial in the signal length. This paper develops a new method, called Chaining Pursuit, for sketching both m-sparse and compressible signals with O(m polylog d) nonadaptive linear measurements. The algorithm can reconstruct the original signal in time O(m polylog d) with an error proportional to the optimal m-term approximation error. In particular, m-sparse signals are recovered perfectly and compressible signals are recovered with polylogarithmic distortion. Moreover, the algorithm can operate in small space O(m polylog d), so it is appropriate for streaming data.

关键词： approximation embedding group testing sketching sparse approximation sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：