| 1 |
// boost-no-inspect |
| 2 |
/* |
| 3 |
* Copyright Nick Thompson, Matt Borland, 2023 |
| 4 |
* Use, modification and distribution are subject to the |
| 5 |
* Boost Software License, Version 1.0. (See accompanying file |
| 6 |
* LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| 7 |
*/ |
| 8 |
|
| 9 |
#ifndef BOOST_MATH_SPECIAL_FOURIER_TRANSFORM_DAUBECHIES_HPP |
| 10 |
#define BOOST_MATH_SPECIAL_FOURIER_TRANSFORM_DAUBECHIES_HPP |
| 11 |
#include <array> |
| 12 |
#include <cmath> |
| 13 |
#include <complex> |
| 14 |
#include <iostream> |
| 15 |
#include <limits> |
| 16 |
#include <boost/math/constants/constants.hpp> |
| 17 |
#include <boost/math/tools/big_constant.hpp> |
| 18 |
#include <boost/math/tools/estrin.hpp> |
| 19 |
|
| 20 |
namespace boost::math { |
| 21 |
|
| 22 |
namespace detail { |
| 23 |
|
| 24 |
// See the Table 6.2 of Daubechies, Ten Lectures on Wavelets. |
| 25 |
// These constants are precisely those divided by 1/sqrt(2), because otherwise |
| 26 |
// we'd immediately just have to divide through by 1/sqrt(2). |
| 27 |
// These numbers agree with Table 6.2, but are generated via example/calculate_fourier_transform_daubechies_constants.cpp |
| 28 |
template <typename Real, unsigned N> constexpr std::array<Real, N> ft_daubechies_scaling_polynomial_coefficients() { |
| 29 |
static_assert(N >= 1 && N <= 10, "Scaling function only implemented for 1-10 vanishing moments."); |
| 30 |
if constexpr (N == 1) { |
| 31 |
return std::array<Real, 1>{static_cast<Real>(1)}; |
| 32 |
} |
| 33 |
if constexpr (N == 2) { |
| 34 |
return {BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 35 |
1.36602540378443864676372317075293618347140262690519031402790348972596650842632007803393058), |
| 36 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 37 |
-0.366025403784438646763723170752936183471402626905190314027903489725966508441952115116994061)}; |
| 38 |
} |
| 39 |
if constexpr (N == 3) { |
| 40 |
return std::array<Real, 3>{ |
| 41 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 42 |
1.88186883113665472301331643028468183320710177910151845853383427363197699204347143889269703), |
| 43 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 44 |
-1.08113883008418966599944677221635926685977756966260841342875242639629721931484516409937898), |
| 45 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 46 |
0.199269998947534942986130341931677433652675790561089954894918152764320227250084833874126086)}; |
| 47 |
} |
| 48 |
if constexpr (N == 4) { |
| 49 |
return std::array<Real, 4>{ |
| 50 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 51 |
2.60642742441038678619616138456320274846457112268350230103083547418823666924354637907021821), |
| 52 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 53 |
-2.33814397690691624172277875654682595239896411009843420976312905955518655953831321619717516), |
| 54 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 55 |
0.851612467139421235087502761217605775743179492713667860409024360383174560120738199344383827), |
| 56 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 57 |
-0.119895914642891779560885389233982571808786505298735951676730775016224669960397338539830347)}; |
| 58 |
} |
| 59 |
if constexpr (N == 5) { |
| 60 |
return std::array<Real, 5>{ |
| 61 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 62 |
3.62270372133693372237431371824382790538377237674943454540758419371854887218301659611796287), |
| 63 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 64 |
-4.45042192340421529271926241961545172940077367856833333571968270791760393243895360839974479), |
| 65 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 66 |
2.41430351179889241160444590912469777504146155873489898274561148139247721271772284677196254), |
| 67 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 68 |
-0.662064156756696785656360678859372223233256033099757083735935493062448802216759690564503751), |
| 69 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 70 |
0.0754788470250859443968634711062982722087957761837568913024225258690266500301041274151679859)}; |
| 71 |
} |
| 72 |
if constexpr (N == 6) { |
| 73 |
return std::array<Real, 6>{ |
| 74 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 75 |
5.04775782409284533508504459282823265081102702143912881539214595513121059428213452194161891), |
| 76 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 77 |
-7.90242489414953082292172067801361411066690749603940036372954720647258482521355701761199), |
| 78 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 79 |
5.69062231972011992229557724635729642828799628244009852056657089766265949751788181912632318), |
| 80 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 81 |
-2.29591465417352749013350971621495843275025605194376564457120763045109729714936982561585742), |
| 82 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 83 |
0.508712486289373262241383448555327418882885930043157873517278143590549199629822225076344289), |
| 84 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 85 |
-0.0487530817792802065667748935122839545647456859392192011752401594607371693280512344274717466)}; |
| 86 |
} |
| 87 |
if constexpr (N == 7) { |
| 88 |
return std::array<Real, 7>{ |
| 89 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 90 |
7.0463635677199166580912954330590360004554457287730448872409828895500755049108034478397642), |
| 91 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 92 |
-13.4339028220058085795120274851204982381087988043552711869584397724404274044947626280185946), |
| 93 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 94 |
12.0571882966390397563079887516068140052534768286900467252199152570563053103366694003818755), |
| 95 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 96 |
-6.39124482303930285525880162640679389779540687632321120940980371544051534690730897661850842), |
| 97 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 98 |
2.07674879424918331569327229402057948161936796436510457676789758815816492768386639712643599), |
| 99 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 100 |
-0.387167532162867697386347232520843525988806810788254462365009860280979111139408537312553398), |
| 101 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 102 |
0.0320145185998394020646198653617061745647219696385406695044576133973761206215673170563538)}; |
| 103 |
} |
| 104 |
if constexpr (N == 8) { |
| 105 |
return std::array<Real, 8>{ |
| 106 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 107 |
9.85031962984351656604584909868313752909650830419035084214249929687665775818153930511533915), |
| 108 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 109 |
-22.1667494032601530437943449172929277733925779301673358406203340024653233856852379126537395), |
| 110 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 111 |
23.8272728452144265698978643079553442578633838793866258585693705776047828901217069807060715), |
| 112 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 113 |
-15.6065825916019064469551268429136774427686552695820632173344334583910793479437661751737998), |
| 114 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 115 |
6.63923943761238270605338141020386331691362835005178161341935720370310013774320917891051914), |
| 116 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 117 |
-1.81462830704498058848677549516134095104668450780318379608495409574150643627578462439190617), |
| 118 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 119 |
0.292393958692487086036895445298600849998803161432207979583488595754566344585039785927586499), |
| 120 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 121 |
-0.0212655694557728487977430067729997866644059875083834396749941173411979591559303697954912042)}; |
| 122 |
} |
| 123 |
if constexpr (N == 9) { |
| 124 |
return std::array<Real, 9>{ |
| 125 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 126 |
13.7856894948673536752299497816200874595462540239049618127984616645562437295073582057283235), |
| 127 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 128 |
-35.79362367743347676734569335180426263053917566987500206688713345532850076082533131311371), |
| 129 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 130 |
44.8271517576868325408174336351944130389504383168376658969692365144162452669941793147313), |
| 131 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 132 |
-34.9081281226625998193992072777004811412863069972654446089639166067029872995118090115016879), |
| 133 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 134 |
18.2858070519930071738884732413420775324549836290768317032298177553411077249931094333824682), |
| 135 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 136 |
-6.53714271572640296907117142447372145396492988681610221640307755553450246302777187366825001), |
| 137 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 138 |
1.5454286423270706293059630490222623728433659436325762803842722481655127844136128434034519), |
| 139 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 140 |
-0.219427682644567750633335191213222483839627852234602683427115193605056655384931679751929029), |
| 141 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 142 |
0.0142452515927832872075875380128473058349984927391158822994546286919376896668596927857450578)}; |
| 143 |
} |
| 144 |
if constexpr (N == 10) { |
| 145 |
return std::array<Real, 10>{ |
| 146 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 147 |
19.3111846872275854185286532829110292444580572106276740012656292351880418629976266671349603), |
| 148 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 149 |
-56.8572892818288577904562616825768121532988312416110097001327598719988644787442373891037268), |
| 150 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 151 |
81.3040184941182201969442916535886223134891624078921290339772790298979750863332417443823932), |
| 152 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 153 |
-73.3067370305702272426402835488383512315892354877130132060680994033122368453226804355121917), |
| 154 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 155 |
45.5029913577892585869595005785056707790215969761054467083138479721524945862678794713356742), |
| 156 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 157 |
-20.0048938122958245128650205249242185678760602333821352917865992073643758821417211689052482), |
| 158 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 159 |
6.18674372398711325312495154772282340531430890354257911422818567803548535981484584999007723), |
| 160 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 161 |
-1.29022235346655645559407302793903682217361613280994725979138999393113139183198020070701239), |
| 162 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 163 |
0.16380852384056875506684562409582514726612462486206657238854671180228210790016298829595125), |
| 164 |
BOOST_MATH_BIG_CONSTANT(Real, std::numeric_limits<Real>::digits, |
| 165 |
-0.00960430880128020906860390254555211461150702751378997239464015046967050703218076318595987803)}; |
| 166 |
} |
| 167 |
} |
| 168 |
|
| 169 |
} // namespace detail |
| 170 |
|
| 171 |
/* |
| 172 |
* Given ω∈ℝ, computes a numerical approximation to 𝓕[𝜙](ω), |
| 173 |
* where 𝜙 is the Daubechies scaling function. |
| 174 |
* Fast and accurate evaluation of these function seems to me to be a rather involved research project, |
| 175 |
* which I have not endeavored to complete. |
| 176 |
* In particular, recovering ~1ULP evaluation is not possible using the techniques |
| 177 |
* employed here-you should use this with the understanding it is good enough for almost |
| 178 |
* all uses with empirical data, but probably doesn't recover enough accuracy |
| 179 |
* for pure mathematical uses (other than graphing-in which case it's fine). |
| 180 |
* The implementation uses an infinite product of trigonometric polynomials. |
| 181 |
* See Daubechies, 10 Lectures on Wavelets, equation 5.1.17, 5.1.18. |
| 182 |
* It uses the factorization of m₀ shown in Corollary 5.5.4 and equation 5.5.5. |
| 183 |
* See more discusion near equation 6.1.1, |
| 184 |
* as well as efficiency gains from equation 7.1.4. |
| 185 |
*/ |
| 186 |
template <class Real, unsigned p> std::complex<Real> fourier_transform_daubechies_scaling(Real omega) { |
| 187 |
// This arg promotion is kinda sad, but IMO the accuracy is not good enough in |
| 188 |
// float precision using this method. Requesting a better algorithm! |
| 189 |
if constexpr (std::is_same_v<Real, float>) { |
| 190 |
return static_cast<std::complex<float>>(fourier_transform_daubechies_scaling<double, p>(static_cast<double>(omega))); |
| 191 |
} |
| 192 |
using boost::math::constants::one_div_root_two_pi; |
| 193 |
using std::abs; |
| 194 |
using std::exp; |
| 195 |
using std::norm; |
| 196 |
using std::pow; |
| 197 |
using std::sqrt; |
| 198 |
using std::cbrt; |
| 199 |
// Equation 7.1.4 of 10 Lectures on Wavelets is singular at ω=0: |
| 200 |
if (omega == 0) { |
| 201 |
return std::complex<Real>(one_div_root_two_pi<Real>(), 0); |
| 202 |
} |
| 203 |
// For whatever reason, this starts returning NaNs rather than zero for |ω|≫1. |
| 204 |
// But we know that this function decays rather quickly with |ω|, |
| 205 |
// and hence it is "numerically zero", even if in actuality the function does not have compact support. |
| 206 |
// Now, should we probably do a fairly involved, exhaustive calculation to see where exactly we should set this threshold |
| 207 |
// and store them in a table? .... yes. |
| 208 |
if (abs(omega) >= sqrt(std::numeric_limits<Real>::max())) { |
| 209 |
return std::complex<Real>(0, 0); |
| 210 |
} |
| 211 |
auto const constexpr lxi = detail::ft_daubechies_scaling_polynomial_coefficients<Real, p>(); |
| 212 |
auto xi = -omega / 2; |
| 213 |
std::complex<Real> phi{one_div_root_two_pi<Real>(), 0}; |
| 214 |
do { |
| 215 |
std::complex<Real> arg{0, xi}; |
| 216 |
auto z = exp(arg); |
| 217 |
phi *= boost::math::tools::evaluate_polynomial_estrin(lxi, z); |
| 218 |
xi /= 2; |
| 219 |
} while (abs(xi) > std::numeric_limits<Real>::epsilon()); |
| 220 |
std::complex<Real> arg{0, omega}; |
| 221 |
// There is no std::expm1 for complex numbers. |
| 222 |
// We may therefore be leaving accuracy gains on the table for small |ω|: |
| 223 |
std::complex<Real> prefactor = (Real(1) - exp(-arg))/arg; |
| 224 |
return phi * static_cast<std::complex<Real>>(pow(prefactor, p)); |
| 225 |
} |
| 226 |
|
| 227 |
template <class Real, unsigned p> std::complex<Real> fourier_transform_daubechies_wavelet(Real omega) { |
| 228 |
// See Daubechies, 10 Lectures on Wavelets, page 193, unlabelled equation in Theorem 6.3.6: |
| 229 |
// 𝓕[ψ](ω) = -exp(-iω/2)m₀(ω/2 + π)^{*}𝓕[𝜙](ω/2) |
| 230 |
if constexpr (std::is_same_v<Real, float>) { |
| 231 |
return static_cast<std::complex<float>>(fourier_transform_daubechies_wavelet<double, p>(static_cast<double>(omega))); |
| 232 |
} |
| 233 |
|
| 234 |
using std::exp; |
| 235 |
using std::pow; |
| 236 |
auto Fphi = fourier_transform_daubechies_scaling<Real, p>(omega/2); |
| 237 |
auto phase = -exp(std::complex<Real>(0, -omega/2)); |
| 238 |
// See Section 6.4 for the sign convention on the argument, |
| 239 |
// as well as Table 6.2: |
| 240 |
auto z = phase; // strange coincidence. |
| 241 |
//auto z = exp(std::complex<Real>(0, -omega/2 - boost::math::constants::pi<Real>())); |
| 242 |
auto constexpr lxi = detail::ft_daubechies_scaling_polynomial_coefficients<Real, p>(); |
| 243 |
auto m0 = std::complex<Real>(pow((Real(1) + z)/Real(2), p))*boost::math::tools::evaluate_polynomial_estrin(lxi, z); |
| 244 |
return Fphi*std::conj(m0)*phase; |
| 245 |
} |
| 246 |
|
| 247 |
} // namespace boost::math |
| 248 |
#endif |