Change search
Link to record
Permanent link

Direct link
BETA
Mai, Vien V.
Publications (4 of 4) Show all publications
Mai, V. V. & Johansson, M. (2019). Noisy Accelerated Power Method for Eigenproblems With Applications. IEEE Transactions on Signal Processing, 67(12), 3287-3299
Open this publication in new window or tab >>Noisy Accelerated Power Method for Eigenproblems With Applications
2019 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 67, no 12, p. 3287-3299Article in journal (Refereed) Published
Abstract [en]

This paper introduces an efficient algorithm for finding the dominant generalized eigenvectors of a pair of symmetric matrices. Combining tools from approximation theory and convex optimization, we develop a simple scalable algorithm with strong theoretical performance guarantees. More precisely, the algorithm retains the simplicity of the well-knownpower method but enjoys the asymptotic iteration complexity of the powerful Lanczos method. Unlike these classic techniques, our algorithm is designed to decompose the overall problem into a series of subproblems that only need to be solved approximately. The combination of good initializations, fast iterative solvers, and appropriate error control in solving the subproblems lead to a linear running time in the input sizes compared to the superlinear time for the traditional methods. The improved running time immediately offers acceleration for several applications. As an example, we demonstrate how the proposed algorithm can be used to accelerate canonical correlation analysis, which is a fundamental statistical tool for learning of a low-dimensional representation of high-dimensional objects. Numerical experiments on real-world datasets confirm that our approach yields significant improvements over the current state of the art.

Place, publisher, year, edition, pages
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 2019
Keywords
Approximation theory, canonical correlation analysis (CCA), Chebyshev polynomial, generalized eigenvalue (GEV) problems, power method, stochastic convex optimization
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-254003 (URN)10.1109/TSP.2019.2908126 (DOI)000469369900004 ()2-s2.0-85066733192 (Scopus ID)
Note

QC 20190814

Available from: 2019-08-14 Created: 2019-08-14 Last updated: 2019-08-14Bibliographically approved
Mai, V. V. & Johansson, M. (2019). NONLINEAR ACCELERATION OF CONSTRAINED OPTIMIZATION ALGORITHMS. In: 2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP): . Paper presented at 44th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), MAY 12-17, 2019, Brighton, ENGLAND (pp. 4903-4907). IEEE
Open this publication in new window or tab >>NONLINEAR ACCELERATION OF CONSTRAINED OPTIMIZATION ALGORITHMS
2019 (English)In: 2019 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), IEEE , 2019, p. 4903-4907Conference paper, Published paper (Refereed)
Abstract [en]

This paper introduces a novel technique for nonlinear acceleration of first-order methods for constrained convex optimization. Previous studies of nonlinear acceleration have only been able to provide convergence guarantees for unconstrained convex optimization. In contrast, our method is able to avoid infeasibility of the accelerated iterates and retains the theoretical performance guarantees of the unconstrained case. We focus on Anderson acceleration of the classical projected gradient descent (PGD) method, but our techniques can easily be extended to more sophisticated algorithms, such as mirror descent. Due to the presence of a constraint set, the relevant fixed-point mapping for PGD is not differentiable. However, we show that the convergence results for Anderson acceleration of smooth fixed-point iterations can be extended to the non-smooth case under certain technical conditions.

Place, publisher, year, edition, pages
IEEE, 2019
Series
International Conference on Acoustics Speech and Signal Processing ICASSP, ISSN 1520-6149
Keywords
Anderson acceleration, constrained optimization, projected gradient descent, semi-smoothness
National Category
Control Engineering
Identifiers
urn:nbn:se:kth:diva-261054 (URN)10.1109/ICASSP.2019.8682962 (DOI)000482554005028 ()2-s2.0-85068981869 (Scopus ID)978-1-4799-8131-1 (ISBN)
Conference
44th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), MAY 12-17, 2019, Brighton, ENGLAND
Note

QC 20191002

Available from: 2019-10-02 Created: 2019-10-02 Last updated: 2019-10-02Bibliographically approved
Mai, V. V. & Johansson, M. (2017). Lock-Free Incremental Coordinate Descent. In: 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017: . Paper presented at IEEE 56th Annual Conference on Decision and Control (CDC), DEC 12-15, 2017, Melbourne, AUSTRALIA. Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>Lock-Free Incremental Coordinate Descent
2017 (English)In: 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017, Institute of Electrical and Electronics Engineers (IEEE), 2017Conference paper, Published paper (Refereed)
Abstract [en]

We study a flexible algorithm for minimizing a sum of component functions, each of which depends on a large number of decision variables. The algorithm combines aspects of incremental gradient method with that of coordinate descent. In contrast to earlier algorithms of this kind, our algorithm is lock-free and does not require synchronization of access to the shared memory. We prove convergence of the algorithm under asynchronous operation and provide explicit bounds on how the solution times depend on the degree of asynchrony. Numerical experiments confirm our theoretical results.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2017
Series
IEEE Conference on Decision and Control, ISSN 0743-1546
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-223858 (URN)10.1109/CDC.2017.8263981 (DOI)000424696902033 ()2-s2.0-85046302816 (Scopus ID)978-1-5090-2873-3 (ISBN)
Conference
IEEE 56th Annual Conference on Decision and Control (CDC), DEC 12-15, 2017, Melbourne, AUSTRALIA
Funder
Swedish Research CouncilKnut and Alice Wallenberg Foundation
Note

QC 20180306

Available from: 2018-03-06 Created: 2018-03-06 Last updated: 2018-06-01Bibliographically approved
Mai, V. V., Shin, W.-Y. & Ishibashi, K. (2017). Wireless Power Transfer for Distributed Estimation in Sensor Networks. IEEE Journal on Selected Topics in Signal Processing, 11(3), 549-562
Open this publication in new window or tab >>Wireless Power Transfer for Distributed Estimation in Sensor Networks
2017 (English)In: IEEE Journal on Selected Topics in Signal Processing, ISSN 1932-4553, E-ISSN 1941-0484, Vol. 11, no 3, p. 549-562Article in journal (Refereed) Published
Abstract [en]

This paper studies power allocation for distributed estimation of an unknown scalar random source in sensor networks with a multiple-antenna fusion center (FC), where wireless sensors are equipped with radio-frequency-based energy harvesting technology. The sensors' observation is locally processed by using an uncoded amplify-and-forward scheme. The processed signals are then sent to the FC, and are coherently combined at the FC, at which the best linear unbiased estimator (BLUE) is adopted for reliable estimation. We aim to solve the following two power allocation problems: 1) minimizing distortion under various power constraints; and 2) minimizing total transmit power under distortion constraints, where the distortion is measured in terms of mean-squared error of the BLUE. Two iterative algorithms are developed to solve the nonconvex problems, which converge at least to a local optimum. In particular, the above algorithms are designed to jointly optimize the amplification coefficients, energy beamforming, and receive filtering. For each problem, a suboptimal design, a single-antenna FC scenario, and a common harvester deployment for collocated sensors, are also studied. Using the powerful semidefinite relaxation framework, our result is shown to be valid for any number of sensors, each with different noise power, and for an arbitrarily number of antennas at the FC.

Place, publisher, year, edition, pages
IEEE, 2017
Keywords
Amplify-and-forwarding, best linear unbiased estimator (BLUE), distributed estimation, mean-squared error (MSE), wireless power transfer (WPT)
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-208265 (URN)10.1109/JSTSP.2017.2678106 (DOI)000399674500009 ()2-s2.0-85018515386 (Scopus ID)
Note

QC 20170622

Available from: 2017-06-22 Created: 2017-06-22 Last updated: 2017-06-22Bibliographically approved
Organisations

Search in DiVA

Show all publications