In many application problems in optimization, one has little or no correlation between problem variables, and such (sparsity) structure is unknown in advance when optimizing without derivatives. We will show that quadratic interpolation models computed by partial l1-minimization recover the Hessian sparsity of the function being modeled. Given a considerable level of sparsity in the unknown Hessian of the function, such models often achieve the accuracy of second order Taylor ones with very few random sample points. Due to the randomness in the sampling process the accuracy of the models is also random, we will discuss how to show convergence of Trust-Region methods when the performance of the models is random. Inspired by the fact that the sparsity on the model should only be in the quadratic terms we discuss the setting of sparse recovery with partially known support.