Provide vector norms

[Mikhail Katliar]

1. Provide functions to calculate Euclidean norm and squared Euclidean norm:

   Scalar n = norm(v);
   Scalar sn = squaredNorm(v);    // often used
   

   There is a function length() which apparently computes the Euclidean norm, but it is confusing. The scientific term is norm and I was looking for this name. Other software like MATLAB, numpy and Eigen3 also call the corresponding function norm.

2. Provide functions to calculate p-norms:

   Scalar lp1 = lpNorm<1>(v);
   Scalar lp2 = lpNorm<2>(v);  // same as Euclidean norm norm(v)
   Scalar lp37 = lpNorm(v, 3.7);   // weird but valid Lp norm with p = 3.7.
   Scalar lp05 = lpNorm(v, 0.5);   // throws std::invalid_argument, p must be >= 1.
   

[Klaus Iglberger]

Hi Mikhail!

Thanks for the important proposal. Vector norms have been on our list for a long time, so far we didn't focus on this topic though. Thanks to you we now have an issue to remind us of this important but missing feature.

Best regards,

Klaus!

[Daniel Baker]

Hi MIkhail,

I'll comment that I've been successfully doing something like the following:

template<typename RowType>
auto norm2(const RowType &a) {
    return ::std::sqrt(::blaze::dot(a, a));
}

The infinity norm can also be calculated with ::blaze::max(::blaze::abs(x)).

I've been using custom sum functions for my vectors for 1-norms, as I haven't been able to find such a function in the documentation or code, though I know it can be accelerated with SIMD instructions.

[Lakshay Garg]

Hello Blaze devs. I am just getting started with Blaze and wanted to contribute to this issue. Is someone working on this or should I give this a try?

Also it would be great if you could point me to the location where I should implement this feature. (I am not familiar with Blaze's structure)

[Klaus Iglberger]

The following code snippets provide implementations for the most common vector and matrix norms (L1, L2 and maximum). Please note that all matrix norms are entrywise norms (in contrast to induced p-norms).

Vector Norms

L1 Norm

template< typename VT, bool TF >
decltype(auto) l1Norm( const DenseVector<VT,TF>& vec )
{
   ElementType_<VT> norm{};

   for( const auto& element : ~vec )
      norm += abs( element );

   return norm;
}


template< typename VT, bool TF >
decltype(auto) l1Norm( const SparseVector<VT,TF>& vec )
{
   ElementType_<VT> norm{};

   for( const auto& element : ~vec )
      norm += abs( element.value() );

   return norm;
}

L2 Norm

template< typename VT, bool TF >
decltype(auto) l2Norm( const Vector<VT,TF>& vec )
{
   return sqrt( dot( ~vec, ~vec ) );
}

Maximum Norm

template< typename VT, bool TF >
decltype(auto) maxNorm( const Vector<VT,TF>& vec )
{
   return max( abs( ~vec ) );
}

Matrix Norms

L1 Norm

template< typename MT, bool SO >
decltype(auto) l1Norm( const DenseMatrix<MT,SO>& mat )
{
   ElementType_<MT> norm{};

   const size_t m( ( SO == rowMajor ) ? (~mat).rows() : (~mat).columns() );

   for( size_t i=0UL; i<m; ++i ) {
      for( auto it=(~mat).begin(i); it!=(~mat).end(i); ++it )
         norm += abs( *it );
   }

   return norm;
}


template< typename MT, bool SO >
decltype(auto) l1Norm( const SparseMatrix<MT,SO>& mat )
{
   ElementType_<MT> norm{};

   const size_t m( ( SO == rowMajor ) ? (~mat).rows() : (~mat).columns() );

   for( size_t i=0UL; i<m; ++i ) {
      for( auto it=(~mat).begin(i); it!=(~mat).end(i); ++it )
         norm += abs( it->value() );
   }

   return norm;
}

L2 Norm

template< typename MT >
decltype(auto) l2Norm( const Matrix<MT,rowMajor>& mat )
{
   ElementType_<MT> norm{};

   const size_t m( (~mat).rows() );

   for( size_t i=0UL; i<m; ++i ) {
      const auto rowi( row( ~mat, i ) );
      norm += dot( rowi, rowi );
   }

   return sqrt( norm );
}

template< typename MT >
decltype(auto) l2Norm( const Matrix<MT,columnMajor>& mat )
{
   ElementType_<MT> norm{};

   const size_t m( (~mat).columns() );

   for( size_t i=0UL; i<m; ++i ) {
      const auto coli( column( ~mat, i ) );
      norm += dot( coli, coli );
   }

   return sqrt( norm );
}

Maximum Norm

template< typename MT, bool SO >
decltype(auto) maxNorm( const Matrix<MT,SO>& mat )
{
   return max( abs( ~mat ) );
}

[Klaus Iglberger]

Hi Lakshay!

Thanks for your enthusiasm to contribute to this issue. Above you will find a straight forward implementation of the most common vector and matrix norms, which should help you to get started. However, these implementations don't adhere to the performance expectations of Blaze: None of these norms runs in parallel and except for the maximum norm and the L2 norm for vectors they are not vectorized. Therefore the task is to provide optimized implementations of these functions.

Note that this issue is very closely related to issue #4. The task list in the description of issue #4 will give you some guidelines what needs to be done. Also please note that we consider this task as a major effort and have estimated that it will likely take a man month to complete.

Best regards,

Klaus!

[Klaus Iglberger]

Summary

The feature has been implemented, tested, optimized, and documented as required. It is immediately available via cloning the Blaze repository and will be officially released in Blaze 3.3.

Vector Norms

norm()

The norm() function computes the L2 norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double l2 = norm( a );

sqrNorm()

The sqrNorm() function computes the squared L2 norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double l2 = sqrNorm( a );

l1Norm()

The l1Norm() function computes the squared L1 norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double l1 = l1Norm( a );

l2Norm()

The l2Norm() function computes the squared L2 norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double l2 = l2Norm( a );

l3Norm()

The l3Norm() function computes the squared L3 norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double l3 = l3Norm( a );

l4Norm()

The l4Norm() function computes the squared L4 norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double l4 = l4Norm( a );

lpNorm()

The lpNorm() function computes the general Lp norm of the given dense or sparse vector, where the norm is specified by either a compile time or a runtime argument:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double lp1 = lpNorm<2>( a );    // Compile time argument
const double lp2 = lpNorm( a, 2.3 );  // Runtime argument

maxNorm()

The maxNorm() function computes the maximum norm of the given dense or sparse vector:

blaze::DynamicVector<double> a;
// ... Resizing and initialization
const double max = maxNorm( a );

Matrix Norms

norm()

The norm() function computes the L2 norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double l2 = norm( A );

sqrNorm()

The sqrNorm() function computes the squared L2 norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double l2 = sqrNorm( A );

l1Norm()

The l1Norm() function computes the squared L1 norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double l1 = l1Norm( A );

l2Norm()

The l2Norm() function computes the squared L2 norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double l2 = l2Norm( A );

l3Norm()

The l3Norm() function computes the squared L3 norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double l3 = l3Norm( A );

l4Norm()

The l4Norm() function computes the squared L4 norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double l4 = l4Norm( A );

lpNorm()

The lpNorm() function computes the general Lp norm of the given dense or sparse matrix, where the norm is specified by either a compile time or a runtime argument:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double lp1 = lpNorm<2>( A );    // Compile time argument
const double lp2 = lpNorm( A, 2.3 );  // Runtime argument

maxNorm()

The maxNorm() function computes the maximum norm of the given dense or sparse matrix:

blaze::DynamicMatrix<double> A;
// ... Resizing and initialization
const double max = maxNorm( A );