Installing CUDA according to the instructions found on NVIDIA's website is a painstaking process because they are making assumptions about certain dependencies that CUDA relies on that are not installed in the default Ubuntu AMI. This was tested with the .deb network installer found https://developer.nvidia.com/cuda-downloads. Below we are going to detail out the steps you want to take and the order you want to take them in order for your cuda install to be succesful. This should also work for Ubuntu desktop/server builds that are having issues installing CUDA.
You want to run the commands below BEFORE you install cuda.deb.
#cuda pre-install process sudo apt-get update sudo apt-get upgrade -y sudo apt-get install -y linux-headers-$(uname -r) sudo apt-get install -y linux-image-generic sudo apt-get install -y linux-source sudo apt-get install -y linux-headers-$(uname -r) sudo add-apt-repository ppa:ubuntu-toolchain-r/test -y sudo apt-get update sudo apt-get install -y g++-4.9 sudo apt-get install -y linux-image-extra-`uname -r` linux-headers-`uname -r` l$
Make sure to complete the Preinstallation process before you attempt to install cuda.
sudo dpkg -i cuda-repo-ubuntu1404_7.5-18_amd64.deb sudo apt-get update sudo apt-get install -y cuda sudo apt-get upgrade cuda #this last step is necessary to make the driver work sudo apt-get install linux-headers-generic linux-headers-virtual linux-image-virtual linux-virtual -y