Chip designers place on-chip sensors to measure local temperatures, thus preventing thermal runaway situations in multicore processing architectures. However, thermal characterization is directly dependent on the number of placed sensors, which should be minimized, while guaranteeing full detection of all hot-spots and worst case temperature gradient. In this paper, we present EigenMaps: a new set of algorithms to recover precisely the overall thermal map from a minimal number of sensors and a near-optimal sensor allocation algorithm. The proposed methods are stable with respect to possible temperature sensor calibration inaccuracies, and achieve significant improvements compared to the state-of-the-art. In particular, we estimate an entire thermal map for an industrial 8-core industrial design within 1"C of accuracy with just four sensors. Moreover, when the measurements are corrupted by noise (SNR of 15 dB), we can achieve the same precision only with 16 sensors.