Computational complexity lower bounds of certain discrete Radon transform approximations
For the computational model where only additions are allowed, the $\Omega(n^2\log n)$ lower bound on operations count with respect to image size $n\times n$ is obtained for two types of the discrete Radon transform implementations: the fast Hough transform and a generic strip pattern class which includes the classical Hough transform, implying the fast Hough transform algorithm asymptotic optimality. The proofs are based on a specific result from the boolean circuits complexity theory and are generalized for the case of boolean $\vee$ binary operation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Sharp Bounds for Generalized Uniformity Testing
We study the problem of generalized uniformity testing \cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we wan…
Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
Finite-sum optimization plays an important role in the area of machine learning, and hence has triggered a surge of interest in recent years. To address this optimization problem, various randomized incremental gradient …
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
We establish optimal Statistical Query (SQ) lower bounds for robustly learning certain families of discrete high-dimensional distributions. In particular, we show that no efficient SQ algorithm with access to an $\epsilo…
Differentially Private Assouad, Fano, and Le Cam
Le Cam's method, Fano's inequality, and Assouad's lemma are three widely used techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under central differential privacy. Our results …
LEMMAReplicable Distribution Testing
We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probability distributions, the goal is to charact…