Depende de como você instalou o CUDA. Se você executou sudo apt-get install <some-package-which-depends-on-CUDA>
e esse pacote foi removido, o CUDA, um pacote instalado automaticamente, será automaticamente removido. A correção simples é marcar os pacotes CUDA como instalados manualmente:
sudo apt-mark manual cuda-\*