260 lines
9.0 KiB
Plaintext
260 lines
9.0 KiB
Plaintext
[/
|
|
Copyright 2018 Nick Thompson
|
|
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt).
|
|
]
|
|
|
|
[section:norms Norms]
|
|
|
|
[heading Synopsis]
|
|
|
|
``
|
|
#include <boost/math/tools/norms.hpp>
|
|
|
|
namespace boost{ namespace math{ namespace tools {
|
|
|
|
template<class Container>
|
|
auto l0_pseudo_norm(Container const & c);
|
|
|
|
template<class ForwardIterator>
|
|
auto l0_pseudo_norm(ForwardIterator first, ForwardIterator last);
|
|
|
|
template<class ForwardIterator>
|
|
size_t hamming_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2);
|
|
|
|
template<class Container>
|
|
size_t hamming_distance(Container const & u, Container const & v);
|
|
|
|
template<class Container>
|
|
auto l1_norm(Container const & c);
|
|
|
|
template<class ForwardIterator>
|
|
auto l1_norm(ForwardIterator first, ForwardIterator last);
|
|
|
|
template<class Container>
|
|
auto l1_distance(Container const & v1, Container const & v2);
|
|
|
|
template<class ForwardIterator>
|
|
auto l1_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2);
|
|
|
|
template<class Container>
|
|
auto l2_norm(Container const & c);
|
|
|
|
template<class ForwardIterator>
|
|
auto l2_norm(ForwardIterator first, ForwardIterator last);
|
|
|
|
template<class Container>
|
|
auto l2_distance(Container const & v1, Container const & v2);
|
|
|
|
template<class ForwardIterator>
|
|
auto l2_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2);
|
|
|
|
template<class Container>
|
|
auto sup_norm(Container const & c);
|
|
|
|
template<class ForwardIterator>
|
|
auto sup_norm(ForwardIterator first, ForwardIterator last);
|
|
|
|
template<class Container>
|
|
auto sup_distance(Container const & v1, Container const & v2);
|
|
|
|
template<class ForwardIterator>
|
|
auto sup_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2);
|
|
|
|
template<class Container>
|
|
auto lp_norm(Container const & c, unsigned p);
|
|
|
|
template<class ForwardIterator>
|
|
auto lp_norm(ForwardIterator first, ForwardIterator last, unsigned p);
|
|
|
|
template<class Container>
|
|
auto lp_distance(Container const & v1, Container const & v2, unsigned p);
|
|
|
|
template<class ForwardIterator>
|
|
auto lp_distance(ForwardIterator first1, ForwardIterator last1, ForwardIterator first2, unsigned p);
|
|
|
|
template<class Container>
|
|
auto total_variation(Container const & c);
|
|
|
|
template<class ForwardIterator>
|
|
auto total_variation(ForwardIterator first, ForwardIterator last);
|
|
|
|
}}}
|
|
``
|
|
|
|
[heading Description]
|
|
|
|
The file `boost/math/tools/norms.hpp` is a set of facilities for computing scalar values traditionally useful in numerical analysis from vectors.
|
|
|
|
Our examples use `std::vector<double>` to hold the data, but this not required.
|
|
In 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`.
|
|
These routines are usable in float, double, long double, and Boost.Multiprecision precision, as well as their complex extensions whenever the computation is well-defined.
|
|
Integral datatypes are supported for most routines.
|
|
|
|
[heading \u2113[super \u221E] norm]
|
|
|
|
Computes the supremum norm of a dataset:
|
|
|
|
std::vector<double> v{-3, 2, 1};
|
|
double sup = boost::math::tools::sup_norm(v.cbegin(), v.cend());
|
|
// sup = 3
|
|
|
|
std::vector<std::complex<double>> v{{0, -8}, {1,1}, {-3,2}};
|
|
// Range call:
|
|
double sup = boost::math::tools::sup_norm(v);
|
|
// sup = 8
|
|
|
|
Supports real, integral, and complex arithmetic.
|
|
Container must be forward iterable and is not modified.
|
|
|
|
[heading \u2113[super \u221E] distance]
|
|
|
|
Computes the supremum norm distance between two vectors:
|
|
|
|
std::vector<double> v{-3, 2, 1};
|
|
std::vector<double> w{6, -2, 1};
|
|
double sup = boost::math::tools::sup_distance(w, v);
|
|
// sup = 9
|
|
|
|
Supports real, integral, and complex arithmetic.
|
|
Container must be forward iterable and is not modified.
|
|
If the input it integral, the output is a double precision float.
|
|
|
|
|
|
[heading \u2113[super /p/] norm]
|
|
|
|
std::vector<double> v{-8, 0, 0};
|
|
double sup = boost::math::tools::lp_norm(v.cbegin(), v.cend(), 7);
|
|
// sup = 8
|
|
|
|
std::vector<std::complex<double>> v{{1, 0}, {0,1}, {0,-1}};
|
|
double sup = boost::math::tools::lp_norm(v.cbegin(), v.cend(), 3);
|
|
// sup = cbrt(3)
|
|
|
|
Supports both real, integral, and complex arithmetic.
|
|
If the input is integral, the output is a double precision float.
|
|
The container must be forward iterable and the contents are not modified.
|
|
|
|
Only 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.
|
|
|
|
[heading \u2113[super /p/] distance]
|
|
|
|
std::vector<double> v{-8, 0, 0};
|
|
std::vector<double> w{8, 0, 0};
|
|
double dist = boost::math::tools::lp_distance(v, w, 7);
|
|
// dist = 16
|
|
|
|
std::vector<std::complex<double>> v{{1, 0}, {0,1}, {0,-1}};
|
|
double dist = boost::math::tools::lp_distance(v, v, 3);
|
|
// dist = 0
|
|
|
|
Supports both real, integral, and complex arithmetic.
|
|
If the input is integral, the output is a double precision float.
|
|
The container must be forward iterable and the contents are not modified.
|
|
|
|
Only supports integer /p/.
|
|
|
|
[heading \u2113[super 0] pseudo-norm]
|
|
|
|
Counts the number of non-zero elements in a container.
|
|
|
|
std::vector<double> v{0,0,1};
|
|
size_t count = boost::math::tools::l0_pseudo_norm(v.begin(), v.end());
|
|
// count = 1
|
|
|
|
Supports real, integral, and complex numbers.
|
|
The container must be forward iterable and the contents are not modified.
|
|
Note that this measure is not robust against numerical noise and is therefore not as useful as (say) the Hoyer sparsity in numerical applications.
|
|
Works with real, complex, and integral inputs.
|
|
|
|
[heading Hamming Distance]
|
|
|
|
Compute the number of non-equal elements between two vectors /w/ and /v/:
|
|
|
|
std::vector<double> v{0,0,1};
|
|
std::vector<double> w{1,0,0};
|
|
size_t count = boost::math::tools::hamming_distance(w, v);
|
|
// count = 2
|
|
|
|
Works for any datatype for which the operator `!=` is defined.
|
|
|
|
[heading \u2113[super 1] norm]
|
|
|
|
The \u2113[super 1] norm is a special case of the \u2113[super /p/] norm, but is much faster:
|
|
|
|
std::vector<double> v{1,1,1};
|
|
double l1 = boost::math::tools::l1_norm(v.begin(), v.end());
|
|
// l1 = 3
|
|
|
|
Requires a forward iterable input, does not modify input data, and works with real, integral, and complex numbers.
|
|
|
|
[heading \u2113[super 1] distance]
|
|
|
|
Computes the \u2113[super 1] distance between two vectors:
|
|
|
|
std::vector<double> v{1,1,1};
|
|
std::vector<double> w{1,1,1};
|
|
double dist = boost::math::tools::l1_distance(w, v);
|
|
// dist = 0
|
|
|
|
Requires a forward iterable inputs, does not modify input data, and works with real, integral, and complex numbers.
|
|
If the input type is integral, the output is a double precision float.
|
|
|
|
|
|
[heading \u2113[super 2] norm]
|
|
|
|
The \u2113[super 2] norm is again a special case of the \u2113[super /p/] norm, but is much faster:
|
|
|
|
std::vector<double> v{1,1,1};
|
|
double l2 = boost::math::tools::l2_norm(v.begin(), v.end());
|
|
// l2 = sqrt(3)
|
|
|
|
Requires a forward iterable input, does not modify input data, and works with real, complex and integral data.
|
|
If the input is integral, the output is a double precision float.
|
|
|
|
|
|
[heading \u2113[super 2] distance]
|
|
|
|
Compute the \u2113[super 2] distance between two vectors /w/ and /v/:
|
|
|
|
std::vector<double> v{1,1,1};
|
|
std::vector<double> w{1,2,1};
|
|
double dist = boost::math::tools::l2_distance(w, v);
|
|
// dist = 1
|
|
|
|
Requires a forward iterable input, does not modify input data, and works with real, complex numbers, and integral data.
|
|
If the input type is integral, the output is a double precision float.
|
|
|
|
|
|
[heading Total Variation]
|
|
|
|
std::vector<double> v{1,1,1};
|
|
double tv = boost::math::tools::total_variation(v.begin(), v.end());
|
|
// no variation in v, so tv = 0.
|
|
v = {0,1};
|
|
double tv = boost::math::tools::total_variation(v.begin(), v.end());
|
|
// variation is 1, so tv = 1.
|
|
std::vector<int> v{1,1,1};
|
|
double tv = boost::math::tools::total_variation(v);
|
|
|
|
The total variation only supports real numbers and integers.
|
|
If the input is integral, the output is a double precision float.
|
|
|
|
All the constituent operations to compute the total variation are well-defined for complex numbers,
|
|
but the computed result is not meaningful; a 2D total variation is more appropriate.
|
|
The container must be forward iterable, and the contents are not modified.
|
|
|
|
As an aside, the total variation is not technically a norm, since /TV(v) = 0/ does not imply /v = 0/.
|
|
However, it satisfies the triangle inequality and is absolutely 1-homogeneous, so it is a seminorm, and hence is grouped with the other norms here.
|
|
|
|
[heading References]
|
|
|
|
* Higham, Nicholas J. ['Accuracy and stability of numerical algorithms.] Vol. 80. Siam, 2002.
|
|
* Mallat, Stephane. ['A wavelet tour of signal processing: the sparse way.] Academic press, 2008.
|
|
* Hurley, Niall, and Scott Rickard. ['Comparing measures of sparsity.] IEEE Transactions on Information Theory 55.10 (2009): 4723-4741.
|
|
|
|
[endsect]
|
|
[/section:norms Norms]
|