Hola, te diría que lo mas importante es dejar de usar ese disco duro y conecta uno nuevo al sistema de seguridad, ya que si sigues escribiendo nuevos videos encima de los borrados será muy complicado recuperarlos.

Como prier intento yo usaría Foremost, lo puedes instalar en cualquier distro Linux.
Manual: https://linuxconfig.org/how-to-recover-deleted-files-with-foremost-on-linux
Una guia en castellano: https://www.solvetic.com/tutoriales/...ivos-borrados/

A modo de ejemplo, si tienes el disco duro conectado en el path /dev/sdb1 y quieres recuperar videos mp4, y que se copien en el path /root/Desktop/recovered, este sería un ejemplo:
foremost -t mp4 -v -q -i /dev/sdb1 -o /root/Desktop/recovered

Si estás en mac o windows hay otras maneras, como disk drill, pero yo recomiendo foremost como he puesto arriba