Let $A$ be an bounded operator on a Hilbert space with ONB $\{e_n\}_n$. I am looking for precise conditions on $\langle e_n, A e_m \rangle$ to guarantee that $A$ is compact (i.e. the limit of finite rank operators). It is known that $A$ is trace-class if $$ \sum_{m} \sum_n|\langle e_n, A e_m \rangle| < \infty $$ and the trace class operators are within the compacts. However, what if $A$ is not trace class? If $A$ were diagonal we know the sufficient and necessary condition is that $$\langle e_n, A e_n \rangle\to 0 \qquad( n\to\infty)\,.$$
However, what if $A$ is not diagonal? Is there a criterion in terms of the decay of $\langle e_n, A e_m \rangle$?
For $m\geq n$, let $A^{m, n}$ be the $m\times m$ matrix given by
$$ A^{m, n}_{i, j} = \left\{\matrix{ 0, & \text{if } i, j\leq n, \cr \langle e_i, Ae_j\rangle , & \text{otherwise}. } \right. $$ For example, $$ A^{3,2} = \pmatrix{ 0 & 0 &\langle e_1, Ae_3\rangle \cr 0 & 0 &\langle e_2, Ae_3\rangle \cr \langle e_3, Ae_1\rangle & \langle e_3, Ae_2\rangle & \langle e_3, Ae_3\rangle }. $$
Theorem. The operator $A$ is compact if and only if $\lim_{m,n\to\infty} \|A^{m, n}\| =0$.
Proof. Let $P_n$ be the orthogonal projection onto the span of the first $n$ basis vectors and notice that, for $m\geq n$, the matrix of $$ P_mAP_m - P_nAP_n $$ coincides with $A^{m,n}$ inside the top left $m\times m$ block of entries, and has zero entries everywhere else. It follows that $$ \|A^{m, n}\| = \| P_mAP_m - P_nAP_n\|, $$ so the condition regarding the limit in the statement is equivalent to $\{P_nAP_n\}_n$ being a Cauchy sequence.
As we are working within the space of bounded operators on a Hilbert space, which is complete, we may replace "Cauchy" by "converging" in the sentence above.
Assuming that this condition is true, that is, that $P_nAP_n$ converges, then the limit operator has the same matrix as $A$ (I'm assuming we are using Physicist's inner-product, which is conjugate linear in the first variable), and hence coincides with $A$. In other words $$ \lim_nP_nAP_n = A. $$ Since $P_nAP_n$ is finite rank, hence compact, and since the space of compact operators is closed, it follows that $A$ is compact. This proves the "if" part. As for the "only if" part, suppose that $A$ is compact. Using that $\{P_n\}_n$ is uniformly bounded and converges to the identity operator in the strong (pointwise) topology one shows that $P_nAP_n$ converges to $A$ in norm, so $\{P_nAP_n\}_n$ is a Cauchy sequence which we have already agreed to be equivalent to the condition in the statement.
Remarks:
Since $A^{m, n}$ is a finite matrix, its norm is (in principle) computable in terms of the $\langle e_i, Ae_j\rangle $, as required.
Computing norms of finite matrices is a hard numerical problem, so this criterion might not be as useful as the OP would like.