That is a very deep question. There was series of papers recently with proof of convergence of gradient descent for overparameterized deep network (for example, Gradient Descent Finds Global Minima of Deep Neural Networks, A Convergence Theory for Deep Learning via Over-Parameterization or Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks). All of them condition proof on random Gaussian distribution of weights. It's important for proofs to consist of two factors:
Random weights make ReLU statistically compressive mapping (up to linear transformation)
Random weights preserve separation of input for any input distribution - that is if input samples are distinguishable network propagation will not make them indistinguishable
Those properties very difficult to reproduce with deterministic matrices, and even if they are reproducible with deterministic matrices NULL-space (domain of adversarial examples) would likely make method impractical, and more important preservation of those properties during gradient descent would likely make method impractical. But overall it's very difficult but not impossible, and may warrant some research in that direction. In analogous situation, there were some results for Restricted Isometry Property for deterministic matrices in compressed sensing.
