Opportunity

Solving a UMLS(unit modulus least squares)/UMQP(unit modulus quadratic program) is a common need in many important applications including MIMO(multiple input multiple output) detection, array pattern synthesis, source localization, radar waveform design, beamforming, and phase synchronization. In particular, MIMO detection and beamforming are key components in 5G technologies. However, UMLS/UMQP problem is generally NP hard (Nondeterministic Polynomial Time) to converge in a timely manner if at all. The invention proposes a coordinate descent (CD) algorithm framework to tackle the UMLS in a more computationally efficient, easy to implement and scalable manner.  The method is extendable to solving UMQP.  

Technology

In many applications like MIMO detection, phase-only array pattern, source localization, unimodular waveform and beamforming, a common goal is to solve a UMLS problem.  A coordinate descent (CD) technique is proposed here to solve UMLS and UMQP problems more efficiently.  Four coordinate selection rules, namely cyclic, randomized, randomly permuted and greedy are devised.  At each iteration, the CD solves a one-dimensional subproblem which is univariate quadratic minimization over a unit circle, resulting in a closed-form solution.  The four CDs are then extended to solve the more general form of UMLS, namely UMQP. 

Advantages

• Current method of solving UMLS/UMQP is by SDR or GP.  It requires either a high computational complexity or suffers from slow convergence rate.  Via applying CD, they will become scalable, computationally simple and converging faster
• Convergence using RCD, RPCD and GCD to a KKT point from any initial value.
• MIMO detection using CCD achieves lower symbol error rate than the GP and the classical zero-forcing detector.

Applications

• The main function of the invention is to solve the UMLS and UMQP more efficiently and converging faster. 
• The improved algorithm is applicable to radar, communications, signal processing, computer vision, and optics. 
• Applications of the invention include array pattern synthesis, source localization, phase synchronization, radar waveform design, as well as the up-and-coming large-scale MIMO detection and phase-only beamforming with massive antennas.