The optimization of k-space sampling for nonlinear sparse MRI reconstruction is phrased as Bayesian experimental design problem. Bayesian inference is approximated by a novel relaxation to standard signal processing primitives, resulting in an efficient optimization algorithm for Cartesian and spiral trajectories. On clinical resolution brain image data from a Siemens 3T scanner, automatically optimized trajectories lead to significantly improved images, compared to standard low-pass, equispaced or variable density randomized designs. Insights into the nonlinear design optimization problem for MR imaging are given.