Conference proceeding
Distribution of WHT recurrences
MATHEMATICS AND COMPUTER SCIENCE III: ALGORITHMS, TREES, COMBINATORICS AND PROBABILITIES, pp.161-162
Trends in Mathematics
01 Jan 2004
Abstract
This work explores the performance of a family of algorithms for computing the Walsh-Hadamard transform (WHT), a useful computation in signal and image processing [1, 2, 5]. The algorithms exhibit a wide range of performance and it is non-trivial to determine which algorithm is optimal on a given computer [4]. This paper provides a theoretical basis for the performance analysis. Performance is modelled by a family of recurrence relations that determine the number of instructions required to execute a given algorithm, and are related to standard divide and conquer recurrences [6, 3]. However, since there are a variable number of recursive parts which can grow to infinity as the input size increases, new techniques are required for their analysis. In the full version of this paper, the minimum, maximum, expected values, and variances are calculated and the limiting distribution is obtained.
Metrics
4 Record Views
Details
- Title
- Distribution of WHT recurrences
- Creators
- P Hitczenko - Drexel University, MathematicsJohnsonH J Huang
- Publication Details
- MATHEMATICS AND COMPUTER SCIENCE III: ALGORITHMS, TREES, COMBINATORICS AND PROBABILITIES, pp.161-162
- Series
- Trends in Mathematics
- Publisher
- Walter De Gruyter
- Number of pages
- 2
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics; Computer Science (Computing)
- Identifiers
- 991019170554904721
UN Sustainable Development Goals (SDGs)
This output has contributed to the advancement of the following goals:
Source: InCites
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Web of Science research areas
- Mathematics, Applied
- Statistics & Probability