A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations Export

@article{citeulike:4704421, abstract = {We introduce a randomized algorithm for computing the minimal-norm solution to an underdetermined system of linear equations. Given an arbitrary full-rank m x n matrix A with m \< n, any m x 1 vector b, and any positive real number epsilon less than 1, the procedure computes an n x 1 vector x approximating to relative precision epsilon or better the n x 1 vector p of minimal Euclidean norm satisfying Ap=b. The algorithm typically requires O(mn log(sqrt(n)/epsilon) + m**3) floating-point operations, generally less than the O(m**2 n) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.}, archivePrefix = {arXiv}, author = {Tygert, Mark}, citeulike-article-id = {4704421}, citeulike-linkout-0 = {http://arxiv.org/abs/0905.4745}, citeulike-linkout-1 = {http://arxiv.org/pdf/0905.4745}, day = {28}, eprint = {0905.4745}, keywords = {article, norm, optimization}, month = {May}, posted-at = {2009-06-01 15:19:48}, priority = {2}, title = {A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations}, url = {http://arxiv.org/abs/0905.4745}, year = {2009} }

TY - JOUR ID - citeulike:4704421 L3 - citeulike-article-id:4704421 N2 - We introduce a randomized algorithm for computing the minimal-norm solution to an underdetermined system of linear equations. Given an arbitrary full-rank m x n matrix A with m < n, any m x 1 vector b, and any positive real number epsilon less than 1, the procedure computes an n x 1 vector x approximating to relative precision epsilon or better the n x 1 vector p of minimal Euclidean norm satisfying Ap=b. The algorithm typically requires O(mn log(sqrt(n)/epsilon) + m**3) floating-point operations, generally less than the O(m**2 n) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm. TI - A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations KW - article KW - norm KW - optimization AU - Tygert, Mark PY - 2009/May/28/ UR - http://arxiv.org/abs/0905.4745 ER -