Matrix CUR decomposition aims at representing a large matrix A with the product C·U·R, where C (resp. R) consists of a small collection of the original columns (resp. rows), and U is a small intermediate matrix connecting C and R. While modern randomized CUR algorithms have provided many efficient methods of choosing representative columns and rows, there hasn't been a method to find the optimal U matrix. In this paper, we present a sublinear-time randomized method to find good choices of the U matrix. Our proposed algorithm treats the task of finding U as a double-sided least squares problem minZ||A - CZR ||F, and is able to guarantee a close-to-optimal solution by solving a down-sampled problem of much smaller size. We provide worst-case analysis on its approximation error relative to theoretical optimal low-rank approximation error, and we demonstrate empirically how this method can improve the approximation of several large-scale real data matrices with a small number of additional computations.