One way is to perform full tomography on the state.  For a state rho residing in a Hilbert space of finite dimension d, the number of measurement settings needed to perform full tomography is O(d^2).  This is somewhat overkill since you are reconstructing the entire state and you only want information on the spectrum.  The spectrum can be extracted by measuring moments Tr[rho^k] for k=2,...,d. From these moments the spectrum can be extracted via symmetric polynomials.  The k-th moment can be measured by starting with k identical copies of the state in a register and one ancillary qubit prepared in the +1 eigenstate of the x basis: |+>= (|0>+|1>)/sqrt(2).  Performing a controlled cyclic shift on the register, with the control on the |1> state of the ancilla, and measuring the Pauli operator X on the ancilla yields the kth moment. 

If you have some prior knowledge that the state is low rank, i.e. close to pure, then compressed sensing will provide a certificate for that assumption and perform tomography with O(d log^2(d)) measurement settings (which are relatively easy Pauli operator measurements).  

May I recommend this just-published booklet by Nicolas Gisin : "Quantum Chance: Nonlocality, Teleportation and Other Quantum Marvels" , which addresses parts of your question.

Nicolas Gisin, with Alain Aspect, is one of the pioneering experimental physicists in the area of entanglement and Bell's theorem