In order to address the problem of multi-target tracking by nonuniform clutter spatial distribution and unknown density, a clutter density estimator based on sparsity order optimization is proposed. Firstly, the clutter set is obtained by eliminating the potential target-originated measurements that fall within the validation gate. Then, the samples of “sparsity order-hypercube volume” are constructed from the clutter set and the corresponding fitting function is established by the support vector regression machine. Furthmore, the sparsity order is optimized online by finding the mininum using the gradient method. Finally, the clutter sparsity estimator is combined by the Gaussian mixture probability hypothesis density to estimate the clutter density and target state in complicated backgroud simultaneously. Simulation results show the effectiveness of the proposed algorithm.