Sampling from a boolean matrix in Eigen

I have a matrix A of this form:

Eigen::Matrix<bool, n, m> A(n, m)

and I want to obtain a random element among the ones that are 'true'. The silly way to do that would be to obtain the number of 'true' elements t, generate a random number between 1 and t and iterate:

//r = random number
int k = 0;
for (int i = 0; i < A.rows(); ++i)
    for (int j = 0; j < A.cols(); ++j)
    {
        if (A(i, j))
            ++k;
        if (k == r)
            std::cout << "(" << i << ", " << j << ")" << std::endl;
    }

This solution is incredibly slow when multiple samples are needed and the matrix is big. Any suggestion as to how I should go about this?

In short: I'd like to find an efficient way to obtain the i-th 'true' element of the above matrix.