Finding salient features in an image, and matching them to their corresponding features in another image is an important step for many vision-based applications. Feature description plays an important role in the feature matching process. A robust feature descriptor must works with a number of image deformations and should be computationally efficient. For resource-limited systems, floating point and complex operations such as multiplication and square root are not desirable. This research first introduces a robust and efficient feature descriptor called PRObability (PRO) descriptor that meets these requirements without sacrificing matching accuracy. The PRO descriptor is further improved by incorporating only affine features for matching. While performing well, PRO descriptor still requires larger descriptor size, higher offline computation time, and more memory space than other binary feature descriptors. SYnthetic BAsis (SYBA) descriptor is developed to overcome these drawbacks. SYBA is built on the basis of a new compressed sensing theory that uses synthetic basis functions to uniquely encode or reconstruct a signal. The SYBA descriptor is designed to provide accurate feature matching for real-time vision applications. To demonstrate its performance, we develop algorithms that utilize SYBA descriptor to localize the soccer ball in a broadcast soccer game video, track ground objects for unmanned aerial vehicle, and perform motion analysis, and improve visual odometry accuracy for advanced driver assistance systems. SYBA provides high feature matching accuracy with computational simplicity and requires minimal computational resources. It is a hardware-friendly feature description and matching algorithm suitable for embedded vision applications.