Ultrasound localization microscopy (ULM) represents a significant advancement over traditional ultrasound (US) imaging, enabling super-resolution (SR) imaging of microvascular structures with unprecedented detail, by using microbubbles (MBs) as highly reflective contrast agents. After injection into the bloodstream, MBs are localized in US images to reconstruct the microvasculature. However, this technique faces a trade-off between MB localization accuracy and acquisition time. Perfusion with low MB concentrations reduces signal overlap and achieves high localization accuracy but requires extended acquisition times. Conversely, higher MB concentrations shorten acquisition times but increase signal overlap, limiting localization precision. Traditionally, ULM consists of five main steps: tissue filtering, MB detection, MB super-localization, tracking, and rendering. In this study, we present a novel approach that combines a robust principal component analysis (RPCA) with a computational SR technique, replacing the first three steps of ULM with a single process based on solving a SR inverse problem. This method isolates MB signals from background noise and enhances the localization of overlapping MBs, thereby improving overall ULM performance. Experimental results from simulated and in vivo data demonstrate that our proposed approach increases the SR factor by up to 30% and enhances the contrast ratio (CR) by 3.5 dB. It also produces comparable results across other image quality metrics. These improvements enable denser, higher-contrast vascular images.