Suppose we have a Matrix of size nxd (n rows, d columns, n>d), and we have a vector of size 1xd (one row).

I would like to find the distance (Euclidean distance) between that 1xd vector, with each of the rows of the matrix separately, and then find the minimum between them all (find the row number that has the minimum distance with our row vector)

Example:

Code: Select all

MatrixXf MAT(6,4);
   MAT =   [ 1 4 2 4
             2 2 3 0
             2 5 6 5
             7 4 7 1
             1 0 0 5
             3 5 4 4 ];

VectorXf VEC(1,4);
   VEC =   [ 2 1 2 2 ];

// Now we want to find this:
VectosXf DISTANCE(6,1);
for (int i=0; i<MAT.rows(); i++)
{
   DISTANCE(i) = (MAT.row(i).cwise() - VEC).norm();
}

// Then find the index of the minimum coefficient in DISTANCE
// ....
// ....
// ....


ps: This is not C++ code, just pseudo-code of an example

Question: I have gone through the documentation + the forum. I noticed there are many tricks that I can use in Eigen to get the best/vectorized code.
-- _What is the fastest way possible to do something like that ?
-- _I just do not know what is the best way to go about it ?
-- _Also is columnwise or rowwise suitable for storing the matrix or the vector, so to be able to do this calculations?

Thanks

hi,

the following should work:

int i;
float min_dist = (mat.rowwise() - vec).rowwise().norm().minCoeff(&i);

mat.row(i) is the closest.

int i;
float min_dist = (mat.rowwise() - vec).rowwise().norm().minCoeff(&i);

PERFECT !

I think for this line of code to work the fastet (easiest memory access), I need to store both my matrix and my vector row-wise instead of the default column-wise of Eigen. So I better use:

Code: Select all

#define EIGEN_DEFAULT_TO_ROW_MAJOR

PS:I know that code can be changed to column wise version, but I'm just asking a question regarding exactly the rowwise version of the code.

_

I tried the suggested code, but it gave me errors like this:

error C2676: binary '-' : 'const Eigen::PartialRedux<ExpressionType,Direction>' does not define this operator or a conversion to a type acceptable to the predefined operator
error C2228: left of '.rowwise' must have class/struct/union
error C2228: left of '.norm' must have class/struct/union
error C2228: left of '.minCoeff' must have class/struct/union

Here is my code:

Code: Select all

#define EIGEN_DEFAULT_TO_ROW_MAJOR
#include <Eigen/Eigen>

int main()
{
   int ni = 100;
   int nj = 100;

   Eigen::MatrixXf m3(2*ni*nj,(int)ni/2);
   Eigen::VectorXf v3((int)ni/2);

   m3 = Eigen::MatrixXf::Random();
   v3 = Eigen::VectorXf::Random();

   Eigen::VectorXf dist_vec ((int)ni/2);
   dist_vec.setZero();

   // First Try
   int i;
   float minDist = (m3.rowwise() - v3).rowwise().norm().minCoeff(&i);

   // Second Try
   // dist_vec = (m3.rowwise() - v3).rowwise().norm();

return 0;
}

I even tried the one using dist_vec to store the vector the results (before calculation of minCoeff, but that one also gave an error regarding the return type.

I am using Eigen 2.0.12 version. Might that be the cause or am I missing something ?

- Mehrdad

I checked: you need the development branch for that to work... this is not implemented in 2.0.12.

There is no need to use EIGEN_DEFAULT_TO_ROW_MAJOR, you can just use row-major order for that matrix:

Code: Select all

typedef Matrix<float,Dynamic,Dynamic,RowMajor> RowMajorMatrixXf;


Now it compiles, but it still gives error when doing cwise-binary operations m3.which occurs at this location:

return m_matrix - extendedTo(other.derived())

where it stems from this line:
ei_assert(lhs.rows() == rhs.rows() && lhs.cols() == rhs.cols());

in which the first condition does not get true.

why is that

I fixed it, it should have been: (m3.colwise() - v3).colwise().norm()

However the performance is much slower than this other way of coding in which I loop over my matrix rows and calculate the distance with my vector, as shown in the code below:

Code: Select all

#define EIGEN_DEFAULT_TO_ROW_MAJOR
#include <Eigen/Eigen>

int main()
{
   int ni = 100;
   int nj = 100;

   Eigen::MatrixXf m3(2*ni*nj,(int)ni/2);
   Eigen::VectorXf v3((int)ni/2);

   m3 = Eigen::MatrixXf::Random();
   v3 = Eigen::VectorXf::Random();

   Eigen::VectorXf dist_vec (2*ni*nj);
   dist_vec.setZero();

   for (int i=0;i<ni*nj*2; i++)
   {
           dist_vec(i) = (m3.row(i) - v3).cwise().square().sum();         
   }

return 0;
}

Also, this code only works with 2.0.12 and cwise() is not there for the development branch.

So my questions:
1) Is that normal to get a slower performance when we use (m3.colwise() - v3).colwise().norm() ? I have tried all different column/row-major vector/matrix combinations.
2) Why do I get an error when doing (m3.row(i) - v3).cwise().square().sum(), specifically for the cwise() operation in the development branch? Is it not there anymore ?

For the performance difference: remember that norm() is computing the square root, while your custom code is not taking square roots. The equivalent of your code is squaredNorm().

For cwise(): it was removed in the development branch and replaced by array() which has different semantics, see:
http://eigen.tuxfamily.org/dox-devel/Ei ... igen3.html

Thanks for the page explaining the difference between Eigen 2 and 3. It helped a lot.

For the performance, I am aware of the difference between norm and squaredNorm speeds. So I actually tried it with squaredNorm. The code I gave you was just a sample of the loop that I showed for clarity. But still the difference is an order of 10. Is it still normal ?

Here I am providing you the exact code to see the time comparison results by yourself:

Code: Select all

#define EIGEN_DEFAULT_TO_ROW_MAJOR
#include <Eigen/Eigen>
#include <ctime>
#include <iostream>

int main()
{
   clock_t start,stop;
   int ni = 100;
   int nj = 100;

   Eigen::MatrixXf m3(2*ni*nj,(int)ni/2);
   Eigen::VectorXf result(2*ni*nj);
   Eigen::Matrix<float,1,Eigen::Dynamic> v3_row((int)ni/2);

   m3.setOnes();
   result.setZero();
   v3_row.setConstant(2);

   // test for the performance of looping
   start = clock();
   for (int repeat = 0; repeat<1000; repeat++)
   {
      for (int i=0;i<ni*nj*2; i++)
      {
         result(i) = (m3.row(i) - v3_row).array().square().sum();         
      }
   }
   stop = clock();
   std::cout << "1000 distance calculations by looping = " << double((stop - start)) / CLOCKS_PER_SEC << " seconds" << std::endl;   


   // test for the performance of row/column-wise operation
   start = clock();
   for (int repeat = 0; repeat<1000; repeat++)
   {
      result = (m3.rowwise() - v3_row).rowwise().squaredNorm();
   }
   stop = clock();
   std::cout << "1000 distance calculations using rowwise= " << double((stop - start)) / CLOCKS_PER_SEC << " seconds" << std::endl;   


   int temp;
   std::cout << std::endl << "put 0 to exit" << std::endl;
   std::cin >> temp;

   return 0;
}


Using the loop over each row I get 2.2 seconds, and using the rowwise calculation I get 10.8 seconds.

Could you tell me why this happens ? Is using rowwise worse than looping ?

It's not normal that rowwise() would be slower. Maybe, you hit a bug in Eigen. It's worth reporting, with your example code, in our bug tracker, to make sure that we don't forget about it. (I don't have time now, I don't know if Gael has).