In this paper, target tracking constrained to short-term linear trajectories is explored. The problem is viewed as an extension of the matrix decomposition problem into low-rank and sparse components by incorporating an additional line constraint. The Cramer–Rao Bound (CRB) for the trajectory estimation is derived; numerical results show that an alternating algorithm which estimates the various components of the trajectory image is near optimal due to proximity to the computed CRB. In addition to the theoretical contribution of incorporating an additional constraint in the estimation problem, the alternating algorithm is applied to real video data and shown to be effective in estimating the trajectory despite it not being exactly linear.