Surgical tool localization is the foundation to a series of advanced surgical functions e.g. image guided surgical navigation. For precise scenarios like surgical tool localization, sophisticated tools and sensitive tissues can be quite close. This requires a higher localization accuracy than general object localization. And it is also meaningful to know the orientation of tools. To achieve these, this paper proposes a Compressive Sensing based Location Encoding scheme, which formulates the task of surgical tool localization in pixel space into a task of vector regression in encoding space. Furthermore with this scheme, the method is able to capture orientation of surgical tools rather than simply outputting horizontal bounding boxes. To prevent gradient vanishing, a novel back-propagation rule for sparse reconstruction is derived. The back-propagation rule is applicable to different implementations of sparse reconstruction and renders the entire network end-to-end trainable. Finally, the proposed approach gives more accurate bounding boxes as well as capturing the orientation of tools, and achieves state-of-the-art performance compared with 9 competitive both oriented and non-oriented localization methods on a mainstream surgical image dataset: m2cai16-tool-locations. A range of experiments support our claim that regression in CSLE space performs better than traditionally detecting bounding boxes in pixel space.