We propose a new approach to indirectly estimate basal properties of ice streams, i.e. bedrock topography and basal slipperiness, from observations of surface topography and surface velocities. We demonstrate how a maximum a posteriori estimate of basal conditions can be determined using a Bayesian inference approach in a combination with an analytical linearisation of the forward model. Using synthetic data we show that for non-linear media and non-linear sliding law only a few forward-step model evaluations are needed for convergence. The forward step is solved with a numerical finite-element model using the full Stokes equations. The Fréchet derivative of the forward function is approximated through analytical small-perturbation solutions. This approximation is a key feature of the method and the effects of this approximation on model performance are analyzed. The number of iterations needed for convergence increases with the amplitude of the basal perturbations, but generally less than ten iterations are needed.