1[/ 2 Copyright 2018 Nick Thompson 3 4 Distributed under the Boost Software License, Version 1.0. 5 (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt). 7] 8 9[section:norms Norms] 10 11[heading Synopsis] 12 13`` 14#include <boost/math/tools/norms.hpp> 15 16namespace boost{ namespace math{ namespace tools { 17 18 template<class Container> 19 auto l0_pseudo_norm(Container const & c); 20 21 template<class ForwardIterator> 22 auto l0_pseudo_norm(ForwardIterator first, ForwardIterator last); 23 24 template<class ForwardIterator> 25 size_t hamming_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2); 26 27 template<class Container> 28 size_t hamming_distance(Container const & u, Container const & v); 29 30 template<class Container> 31 auto l1_norm(Container const & c); 32 33 template<class ForwardIterator> 34 auto l1_norm(ForwardIterator first, ForwardIterator last); 35 36 template<class Container> 37 auto l1_distance(Container const & v1, Container const & v2); 38 39 template<class ForwardIterator> 40 auto l1_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2); 41 42 template<class Container> 43 auto l2_norm(Container const & c); 44 45 template<class ForwardIterator> 46 auto l2_norm(ForwardIterator first, ForwardIterator last); 47 48 template<class Container> 49 auto l2_distance(Container const & v1, Container const & v2); 50 51 template<class ForwardIterator> 52 auto l2_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2); 53 54 template<class Container> 55 auto sup_norm(Container const & c); 56 57 template<class ForwardIterator> 58 auto sup_norm(ForwardIterator first, ForwardIterator last); 59 60 template<class Container> 61 auto sup_distance(Container const & v1, Container const & v2); 62 63 template<class ForwardIterator> 64 auto sup_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2); 65 66 template<class Container> 67 auto lp_norm(Container const & c, unsigned p); 68 69 template<class ForwardIterator> 70 auto lp_norm(ForwardIterator first, ForwardIterator last, unsigned p); 71 72 template<class Container> 73 auto lp_distance(Container const & v1, Container const & v2, unsigned p); 74 75 template<class ForwardIterator> 76 auto lp_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, unsigned p); 77 78 template<class Container> 79 auto total_variation(Container const & c); 80 81 template<class ForwardIterator> 82 auto total_variation(ForwardIterator first, ForwardIterator last); 83 84}}} 85`` 86 87[heading Description] 88 89The file `boost/math/tools/norms.hpp` is a set of facilities for computing scalar values traditionally useful in numerical analysis from vectors. 90 91Our examples use `std::vector<double>` to hold the data, but this not required. 92In general, you can store your data in an Eigen array, an Armadillo vector, `std::array`, and for many of the routines, a `std::forward_list`. 93These routines are usable in float, double, long double, and Boost.Multiprecision precision, as well as their complex extensions whenever the computation is well-defined. 94Integral datatypes are supported for most routines. 95 96[heading \u2113[super \u221E] norm] 97 98Computes the supremum norm of a dataset: 99 100 std::vector<double> v{-3, 2, 1}; 101 double sup = boost::math::tools::sup_norm(v.cbegin(), v.cend()); 102 // sup = 3 103 104 std::vector<std::complex<double>> v{{0, -8}, {1,1}, {-3,2}}; 105 // Range call: 106 double sup = boost::math::tools::sup_norm(v); 107 // sup = 8 108 109Supports real, integral, and complex arithmetic. 110Container must be forward iterable and is not modified. 111 112[heading \u2113[super \u221E] distance] 113 114Computes the supremum norm distance between two vectors: 115 116 std::vector<double> v{-3, 2, 1}; 117 std::vector<double> w{6, -2, 1}; 118 double sup = boost::math::tools::sup_distance(w, v); 119 // sup = 9 120 121Supports real, integral, and complex arithmetic. 122Container must be forward iterable and is not modified. 123If the input it integral, the output is a double precision float. 124 125 126[heading \u2113[super /p/] norm] 127 128 std::vector<double> v{-8, 0, 0}; 129 double sup = boost::math::tools::lp_norm(v.cbegin(), v.cend(), 7); 130 // sup = 8 131 132 std::vector<std::complex<double>> v{{1, 0}, {0,1}, {0,-1}}; 133 double sup = boost::math::tools::lp_norm(v.cbegin(), v.cend(), 3); 134 // sup = cbrt(3) 135 136Supports both real, integral, and complex arithmetic. 137If the input is integral, the output is a double precision float. 138The container must be forward iterable and the contents are not modified. 139 140Only supports integral /p/ for two reasons: The computation is much slower for real /p/, and the non-integral \u2113[super /p/] norm is rarely used. 141 142[heading \u2113[super /p/] distance] 143 144 std::vector<double> v{-8, 0, 0}; 145 std::vector<double> w{8, 0, 0}; 146 double dist = boost::math::tools::lp_distance(v, w, 7); 147 // dist = 16 148 149 std::vector<std::complex<double>> v{{1, 0}, {0,1}, {0,-1}}; 150 double dist = boost::math::tools::lp_distance(v, v, 3); 151 // dist = 0 152 153Supports both real, integral, and complex arithmetic. 154If the input is integral, the output is a double precision float. 155The container must be forward iterable and the contents are not modified. 156 157Only supports integer /p/. 158 159[heading \u2113[super 0] pseudo-norm] 160 161Counts the number of non-zero elements in a container. 162 163 std::vector<double> v{0,0,1}; 164 size_t count = boost::math::tools::l0_pseudo_norm(v.begin(), v.end()); 165 // count = 1 166 167Supports real, integral, and complex numbers. 168The container must be forward iterable and the contents are not modified. 169Note that this measure is not robust against numerical noise and is therefore not as useful as (say) the Hoyer sparsity in numerical applications. 170Works with real, complex, and integral inputs. 171 172[heading Hamming Distance] 173 174Compute the number of non-equal elements between two vectors /w/ and /v/: 175 176 std::vector<double> v{0,0,1}; 177 std::vector<double> w{1,0,0}; 178 size_t count = boost::math::tools::hamming_distance(w, v); 179 // count = 2 180 181Works for any datatype for which the operator `!=` is defined. 182 183[heading \u2113[super 1] norm] 184 185The \u2113[super 1] norm is a special case of the \u2113[super /p/] norm, but is much faster: 186 187 std::vector<double> v{1,1,1}; 188 double l1 = boost::math::tools::l1_norm(v.begin(), v.end()); 189 // l1 = 3 190 191Requires a forward iterable input, does not modify input data, and works with real, integral, and complex numbers. 192 193[heading \u2113[super 1] distance] 194 195Computes the \u2113[super 1] distance between two vectors: 196 197 std::vector<double> v{1,1,1}; 198 std::vector<double> w{1,1,1}; 199 double dist = boost::math::tools::l1_distance(w, v); 200 // dist = 0 201 202Requires a forward iterable inputs, does not modify input data, and works with real, integral, and complex numbers. 203If the input type is integral, the output is a double precision float. 204 205 206[heading \u2113[super 2] norm] 207 208The \u2113[super 2] norm is again a special case of the \u2113[super /p/] norm, but is much faster: 209 210 std::vector<double> v{1,1,1}; 211 double l2 = boost::math::tools::l2_norm(v.begin(), v.end()); 212 // l2 = sqrt(3) 213 214Requires a forward iterable input, does not modify input data, and works with real, complex and integral data. 215If the input is integral, the output is a double precision float. 216 217 218[heading \u2113[super 2] distance] 219 220Compute the \u2113[super 2] distance between two vectors /w/ and /v/: 221 222 std::vector<double> v{1,1,1}; 223 std::vector<double> w{1,2,1}; 224 double dist = boost::math::tools::l2_distance(w, v); 225 // dist = 1 226 227Requires a forward iterable input, does not modify input data, and works with real, complex numbers, and integral data. 228If the input type is integral, the output is a double precision float. 229 230 231[heading Total Variation] 232 233 std::vector<double> v{1,1,1}; 234 double tv = boost::math::tools::total_variation(v.begin(), v.end()); 235 // no variation in v, so tv = 0. 236 v = {0,1}; 237 double tv = boost::math::tools::total_variation(v.begin(), v.end()); 238 // variation is 1, so tv = 1. 239 std::vector<int> v{1,1,1}; 240 double tv = boost::math::tools::total_variation(v); 241 242The total variation only supports real numbers and integers. 243If the input is integral, the output is a double precision float. 244 245All the constituent operations to compute the total variation are well-defined for complex numbers, 246but the computed result is not meaningful; a 2D total variation is more appropriate. 247The container must be forward iterable, and the contents are not modified. 248 249As an aside, the total variation is not technically a norm, since /TV(v) = 0/ does not imply /v = 0/. 250However, it satisfies the triangle inequality and is absolutely 1-homogeneous, so it is a seminorm, and hence is grouped with the other norms here. 251 252[heading References] 253 254* Higham, Nicholas J. ['Accuracy and stability of numerical algorithms.] Vol. 80. Siam, 2002. 255* Mallat, Stephane. ['A wavelet tour of signal processing: the sparse way.] Academic press, 2008. 256* Hurley, Niall, and Scott Rickard. ['Comparing measures of sparsity.] IEEE Transactions on Information Theory 55.10 (2009): 4723-4741. 257 258[endsect] 259[/section:norms Norms] 260