2015/10/05 by Matthew R. Reynolds, Alireza Doostan, Reynolds, Matthew +3
Mathematics · Physics and Astronomy · Engineering · #Tensor decomposition and applications #Electromagnetic Scattering and Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1510.01398
This paper introduces a randomized variation of the alternating least squares\n(ALS) algorithm for rank reduction of canonical tensor formats. The aim is to\naddress the potential numerical ill-conditioning of least squares matrices at\neach ALS iteration. The proposed algorithm, dubbed randomized ALS, mitigates\nlarge condition numbers via projections onto random tensors, a technique\ninspired by well-established randomized projection methods for solving\noverdetermined least squares problems in a matrix setting. A probabilistic\nbound on the condition numbers of the randomized ALS matrices is provided,\ndemonstrating reductions relative to their standard counterparts. Additionally,\nresults are provided that guarantee comparable accuracy of the randomized ALS\nsolution at each iteration. The performance of the randomized algorithm is\nstudied with three examples, including manufactured tensors and an elliptic PDE\nwith random inputs. In particular, for the latter, tests illustrate not only\nimprovements in condition numbers, but also improved accuracy of the iterative\nsolver for the PDE solution represented in a canonical tensor format.\n