Given a symmetric linear function $L\colon\mathbb R^N \to \mathbb R^N$, $N\ggg 0$, do there exist (possibly probabilistic) iterative tests for positive definiteness? Ideally I am looking for an algorithm that can either provide some bounds on the largest negative eigenvalue, or put some probability on the chance of $L$ being positive definite, in the sense of a Chebyshev-type inequality $\Pr(\lambda_{\min}(L)<0) \le a_n$ (with $a_N$=0 if $L$ is in fact psd.)
In this context $N$ is so large that the matrix associated with $L$ cannot be kept in memory, and we likely only can afford a small number of iterations - at most $\mathcal O(\sqrt N)$, but preferably $\mathcal O(\log N)$.