This paper presents the robust velocity estimation of an omnidirectional mobile robot using a polygonal array of optical mice that are installed at the bottom of the mobile robot. First, the velocity kinematics from a mobile robot to an array of optical mice is derived as an overdetermined linear system. The least squares velocity estimate of a mobile robot is then obtained, which becomes the same as the simple average for a regular polygonal arrangement of optical mice. Next, several practical issues that need be addressed for the use of the least squares mobile robot velocity estimation using optical mice are investigated, which include measurement noises, partial malfunctions, and imperfect installation. Finally, experimental results with different number of optical mice and under different floor surface conditions are given to demonstrate the validity and performance of the proposed least squares mobile robot velocity estimation method.