  In this paper we consider symmetric, positive semidefinite (SPSD) matrix $A$
and present two algorithms for computing the $p$-Schatten norm $\|A\|_p$. The
first algorithm works for any SPSD matrix $A$. The second algorithm works for
non-singular SPSD matrices and runs in time that depends on $\kappa =
{\lambda_1(A)\over \lambda_n(A)}$, where $\lambda_i(A)$ is the $i$-th
eigenvalue of $A$. Our methods are simple and easy to implement and can be
extended to general matrices. Our algorithms improve, for a range of
parameters, recent results of Musco, Netrapalli, Sidford, Ubaru and Woodruff
(ITCS 2018) and match the running time of the methods by Han, Malioutov, Avron,
and Shin (SISC 2017) while avoiding computations of coefficients of Chebyshev
polynomials.
