IP Library › Granted Patent US 12,574,861
Granted Patent B2
US 12,574,861 · App. 17/662,696 · Granted Mar 10, 2026

Method and system for accelerating distributed principal components with noisy channels

Inventors: Vincent Kin Nang Lau (New Territories, HK); Zezhong Zhang (Shenzhen, CN); Kaibin Huang (New Territories, HK)
Assignee: The Hong Kong University of Science and Technology
H04W52/36H04L5/006H04L5/0073
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,574,861
App. No.
17/662,696
Granted
Mar 10, 2026
Kind
B2
Abstract

The described technology is generally directed towards accelerating distributed principal components in the presence of noisy channels. A federated training based method is disclosed. The method can calculate a desired common subspace for edge devices under the coordination of a server. The server can be connected to the edge devices via noisy wireless channels. A broadband communication system can be used, wherein devices can transmit local gradients by linear analog modulation over sub-channels in communication rounds for over-the-air aggregation. Before each communication round, the server can detect information of a current region. Based on the region information, an online region-adaptive power control scheme can be applied to accelerate the process.

Claims (50)

1 . A method, comprising:

receiving, by a first device comprising at least one processor, an updated matrix from a server, wherein the first device is a participant in a federated principal components analysis;

determining, by the first device, a local gradient with respect to the updated matrix, wherein the local gradient is based on local data stored at the first device;

modulating, by the first device, the local gradient using linear analog modulation, resulting in a modulated local gradient;

adjusting, by the first device, a transmission power, resulting in an adjusted transmission power, wherein the adjusting is performed according to a defined region-adaptive control process that:

decreases transmission power in response to determining that a descent region detected at the server comprises a saddle region, or

increases transmission power in response to determining that the descent region comprises a non-stationary region or a defined optimum region; and

sending, by the first device, the modulated local gradient to the server via a first wireless signal, wherein the first wireless signal comprises the adjusted transmission power, and wherein the first wireless signal is synchronized with a second wireless signal sent by a second device.

2 . The method of claim 1 , wherein decreasing the transmission power is performed in order to increase noise in the first wireless signal and thereby enable escape from the saddle region detected at the server.

3 . The method of claim 1 , wherein increasing the transmission power comprises increasing the transmission power in order to use power that was previously saved by decreasing the transmission power.

4 . The method of claim 1 , wherein the method is performed in multiple repeating cycles.

5 . The method of claim 1 , wherein the method is repeated to enable a determination, at the server, of a lower-dimensional subspace that contains information from higher-dimensional data including the local data stored at the first device and other local data stored at other devices.

6 . The method of claim 1 , further comprising receiving, by the first device, synchronization information to synchronize the first wireless signal with the second wireless signal.

7 . The method of claim 1 , wherein adjusting the transmission power according to the defined region-adaptive control process further comprises performing at least one of a defined one-shot power-spending process in which saved power is used in a single subsequent round, or a defined gradual power-spending process in which saved power is distributed across multiple rounds.

8 . Server equipment configured to participate in a federated principal components analysis, the server equipment comprising:

at least one processor; and

at least one memory that stores executable instructions that, when executed by the at least one processor, facilitate performance of operations, comprising:

receiving an aggregated signal comprising a global gradient,

wherein the global gradient comprises a combination of respective local gradients calculated at respective devices,

wherein the respective local gradients are concurrently wirelessly transmitted by the respective devices for over the air combination of the respective local gradients to form the aggregated signal;

updating a matrix based on the global gradient, resulting in an updated matrix;

determining a region type associated with the global gradient;

determining whether the region type comprises a saddle region, a non-stationary region, or a defined optimum region;

determining, based on the region type, a power adjustment for application by the respective devices, wherein the power adjustment comprises:

reducing transmission power in response to the region type being determined to correspond to the saddle region, or

increasing transmission power in response to the region type being determined to correspond to the non-stationary region or the defined optimum region; and

sending the updated matrix and control information identifying the power adjustment and the power adjustment to the respective devices.

9 . The server equipment of claim 8 , wherein the decrease of the transmission power effectuates an increase in noise included in wireless transmissions by the respective devices, and wherein the increase in noise enables escape from the saddle region.

10 . The server equipment of claim 8 , wherein increasing the transmission power comprises an increase of the transmission power in order to enable use by the respective devices of power that was previously saved by the decrease of the transmission power.

11 . The server equipment of claim 8 , wherein the operations are is performed in multiple repeating cycles according to a defined frequency.

12 . The server equipment of claim 8 , wherein the operations are repeated to enable calculation of a lower-dimensional subspace that contains information from higher-dimensional data including respective local data stored at the respective devices.

13 . The server equipment of claim 8 , wherein the operations further comprise sending synchronization information to synchronize concurrent wireless transmissions of the respective local gradients by the respective devices.

14 . A non-transitory machine-readable medium, comprising executable instructions that, when executed by at least one processor, facilitate performance of operations, comprising:

participating, by a device of multiple devices, in a federated principal components analysis,

wherein the federated principal components analysis comprises multiple communication rounds,

wherein each communication round of the multiple communication rounds comprises a simultaneous wireless transmission from the multiple devices to a server, and

wherein the operations of each communication round further comprise:

receiving an updated matrix from the server;

determining a local gradient with respect to the updated matrix, wherein the local gradient is based on local data stored at the device;

modulating the local gradient using linear analog modulation, resulting in a modulated local gradient;

adjusting a transmission power, resulting in an adjusted transmission power, wherein the adjusting is performed according to a defined region-adaptive control process that:

reduces transmission power when a descent region detected at the server is determined to comprise a potential saddle region, or

increases transmission power when the descent region is determined to comprise a non-stationary region or a defined optimum region; and

concurrently wirelessly transmitting the modulated local gradient to the server via a wireless signal, wherein the wireless signal comprises the adjusted transmission power, and wherein the wireless signal is simultaneous with multiple wireless signals sent by the multiple devices.

15 . The non-transitory machine-readable medium of claim 14 , wherein the transmission power is reduced in order to increase noise in the wireless signal and thereby enable avoidance of the potential saddle region detected at the server.

16 . The non-transitory machine-readable medium of claim 14 , wherein the transmission power is increased in order to use power that was previously saved by decreasing the transmission power.

17 . The non-transitory machine-readable medium of claim 14 , wherein the federated principal components analysis enables a determination, at the server, of a lower-dimensional subspace that contains information from higher-dimensional data including local data stored at the multiple devices.

18 . The non-transitory machine-readable medium of claim 14 , wherein the operations are performed in multiple repeating cycles according to a defined frequency.

19 . The non-transitory machine-readable medium of claim 14 , wherein the wireless signal is synchronized with another wireless signal of the with multiple wireless signals.

20 . The non-transitory machine-readable medium of claim 14 , wherein adjusting the transmission power according to the defined region-adaptive control process further comprises performing at least one of a defined one-shot power-spending process in which saved power is used in a single subsequent round, or a defined gradual power-spending process in which saved power is distributed across multiple rounds.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 10, 2022
From: LAU, VINCENT KIN NANG; ZHANG, ZEZHONG; HUANG, KAIBIN
To: THE HONG KONG UNIVERSITY OF SCIENCE AND TECHNOLOGY
Reel/Frame 059879/0936 →
Continuity (2)
Provisional Application 63193042 · May 25, 2021
Related Publication 20220394629A1 · Dec 8, 2022
References Cited (59)
US 10922620B2 · Mytkowicz et al. · 2021 [cited by applicant]
US 20180013681A1 · Kohout et al. · 2018 [cited by applicant]
US 20180365582A1 · Musuvathi et al. · 2018 [cited by applicant]
US 20230413070A1 · Li · 2023 [cited by examiner]
CN 109359150 · 2019 [cited by applicant]
CN 109379120A · 2019 [cited by applicant]
CN 109471850 · 2019 [cited by applicant]
CN 111737749A · 2020 [cited by applicant]
CN 112232359A · 2021 [cited by applicant]
Jialin Dong, Student Member, IEEE, Yuanming Shi, Member, IEEE, and Zhi Ding, Fellow, IEEE; Blind Over-the-Air Computation and Data Fusion via Provable Wirtinger Flow; arXiv:1811.04644v1; Nov. 12, 2018; (Year: 2018). [cited by examiner]
Jialin Dong, Blind Over-the-Air Computation and Data Fusion via Provable Wirtinger Flow, Nov. 12, 2018, arXiv:1811.04644v1 (Year: 2018). [cited by examiner]
Gafni et al., “Federated Learning: A Signal Processing Perspective,” arXiv:2103.17150v1 [ eess.SP] Mar. 31, 2021, 25 pages. [cited by applicant]
Narayanamurthy et al., “Federated Over-the-Air Subspace Learning and Tracking from Incomplete Data,” arXiv:2002.12873v2 [cs.LG] Jun. 14, 2020, 33 pages. [cited by applicant]
Ni et al., “Integrating Over-the-Air Federated Learning and Non-Orthogonal Multiple Access: What Role can RIS Play?” arXiv:2103.00435v1 [cs.IT] Feb. 28, 2021, 14 pages. [cited by applicant]
Wang et al., “Optimizing Federated Learning on Non-IID Data with Reinforcement Learning,” IEEE Infocom 2020—EEE Conference on Computer Communications, Jul. 1, 2020, 10 pages. [cited by applicant]
Sery et al., “Over-the-Air Federated Learning from Heterogeneous Data,” arXiv:2009.12787v2 [cs.LG] Oct. 2, 2020, 15 pages. [cited by applicant]
Abdi et al., “Principal component analysis,” Wiley Interdiscip. Rev. Comput. Stat., vol. 2, No. 4, pp. 433-459, Jul. 15, 2010, 27 pages. [cited by applicant]
Wang et al., “PCA-Based Channel Estimation and Tracking for Massive MIMO Systems With Uniform Rectangular Arrays,” IEEE Trans. Wireless Commun., vol. 19, pp. 6786-6797, Oct. 2020, 13 pages. [cited by applicant]
Belhumeur et al., “Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 19, pp. 711-720, Jul. 1997, 10 pages. [cited by applicant]
Zhu et al., “Broadband Analog Aggregation for Low-Latency Federated Edge Learning (Extended Version),” arXiv:1812.11494v3 [cs.IT] Jan. 16, 2019, 30 pages. [cited by applicant]
Zhu et al., “MIMO Over-the-Air Computation for High-Mobility Multi-Modal Sensing,” arXiv:1803.11129v2 [cs.IT] Jul. 12, 2018, 14 pages. [cited by applicant]
Mcmahan et al., “Communication-efficient learning of deep networks from decentralized data,” in Proc. Int. Conf. Artif. Int. Statist. (AISTATS), pp. 1273-1282, 2017, 10 pages. [cited by applicant]
Grammenos et al., “Federated Principal Component Analysis,” arXiv:1907.08059v3 [cs.LG] Oct. 22, 2020, 36 pages. [cited by applicant]
Fan et al., “Distributed estimation of principal eigenspaces,” arXiv:1702.06488v4 [stat.CO] Jan. 10, 2018, 47 pages. [cited by applicant]
Balcan et al., “Improved Distributed Principal Component Analysis,” in Proc. Conf. Neural Inf. Process. Syst. (NIPS), vol. 27, 2014, 9 pages. [cited by applicant]
Friedlander et al., “Erratum: Hybrid deterministic-stochastic methods for data fitting,” SIAM J. Sci. Comput., vol. 35, No. 4, pp. B950-B951, 2013, 2 pages. [cited by applicant]
Yang et al., “Projection approximation subspace tracking,” IEEE Trans. Signal Process., vol. 43, pp. 95-107, Jan. 1995, 13 pages. [cited by applicant]
Zhang et al., “Turning Channel Noise into an Accelerator for Over-the-Air Principal Component Analysis,” arXiv:2104.10095v3 [cs.IT] Apr. 1, 2022, 16 pages. [cited by applicant]
Wold et al., “Principal Component Analysis,” Chemometrics and Intelligent Laboratory Systems, 2 (1987) 37-52, 16 pages. [cited by applicant]
Iwen et al., “A Distributed and Incremental SVD Algorithm for Agglomerative Data Analysis on Large Networks,” Siam J. Matrix Anal. Appl, vol. 37, No. 4, pp. 1699-1718, 20 pages. [cited by applicant]
“Kxwfspz / AirPCA,” Github, https://github.com/Kxwfspz/AirPCA, accessed Apr. 20, 2022, 1 page. [cited by applicant]
Narayanamurthy et al., “Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data,” arXiv:2002.12873v3 [cs.LG] Jun. 22, 2021, 41 pages. [cited by applicant]
Ni et al., “Integrating Over-the-Air Federated Learning and Non-Orthogonal Multiple Access: What Role can RIS Play?” arXiv:2103.00435v1 [cs.IT] Feb. 28, 2021, 15 pages. [cited by applicant]
Lim et al., “Federated learning in mobile edge networks : a comprehensive survey,” IEEE Communications Surveys and Tutorials, 22(3), 2031-2063, 34 pages. [cited by applicant]
Sun et al., “Principal Component Analysis-Based Broadband Hybrid Precoding for Millimeter-Wave Massive MIMO Systems,” IEEE Transactions on Wireless Communications (vol. 19, Issue: 10, Oct. 2020), 16 pages. [cited by applicant]
Bartlett et al., “Face Recognition by Independent Component Analysis,” IEEE Trans Neural Netw. 2002 ; 13(6): 1450-1464, 42 pages. [cited by applicant]
Zhu et al., “MIMO Over-the-Air Computation for High-Mobility Multi-Modal Sensing,” IEEE Internet of Things Journal (vol. 6, Issue: 4, Aug. 2019), 14 pages. [cited by applicant]
Oja et al., “On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix,” J. Math. Anal. Appl., vol. 106, No. 1, pp. 69-84, 1985, 16 pages. [cited by applicant]
Chen et al., “A Joint Learning and Communications Framework for Federated Learning over Wireless Networks,” IEEE Transactions on Wireless Communications ( vol. 20, Issue: 1, Jan. 2021), 14 pages. [cited by applicant]
Yang et al., “Scheduling Policies for Federated Learning in Wireless Networks,” arXiv:1908.06287v2 [cs.IT] Oct. 9, 2019, 16 pages. [cited by applicant]
Du et al., “High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning,” IEEE Transactions on Signal Processing (vol. 68), pp. 2128-2142, Mar. 2020, 15 pages. [cited by applicant]
Shlezinger et al., “UVeQFed: Universal Vector Quantization for Federated Learning,” IEEE Transactions on Signal Processing, vol. 69, 2021, 15 pages. [cited by applicant]
Luo et al., “HFEL: Joint Edge Association and Resource Allocation for Cost-Efficient Hierarchical Federated Edge Learning,” IEEE Transactions on Wireless Communications ( vol. 19, Issue: 10, Oct. 2020), 14 pages. [cited by applicant]
Yang et al., “Energy Efficient Federated Learning Over Wireless Communication Networks,” IEEE Transactions on Wireless Communications ( vol. 20, Issue: 3, Mar. 2021), pp. 1935-1949, 15 pages. [cited by applicant]
Zeng et al., “Energy-Efficient Resource Management for Federated Edge Learning With CPU-GPU Heterogeneous Computing,” arXiv:2007.07122v2 [cs.IT] Jul. 15, 2020, 35 pages. [cited by applicant]
Mo et al., “Energy-Efficient Federated Edge Learning with Joint Communication and Computation Design,” Journal of Communications and Information Networks, vol. 6, No. 2, Jun. 2021, 15 pages. [cited by applicant]
Zhai et al., “Hybrid Beamforming for Massive MIMO Over-the-Air Computation,” IEEE Transactions on Communications, vol. 69, No. 4, Apr. 2021, 15 pages. [cited by applicant]
Zhang et al., “Gradient Statistics Aware Power Control for Over-the-Air Federated Learning,” IEEE Trans. Wireless Commun., vol. 20, pp. 5115-5128, Aug. 2021, 14 pages. [cited by applicant]
Samarakoon et al., “Distributed Federated Learning for Ultra-Reliable Low-Latency Vehicular Communications,” IEEE Transactions on Communications (vol. 68, Issue: 2, Feb. 2020), 14 pages. [cited by applicant]
Amiri et al., “Federated Learning Over Wireless Fading Channels,” IEEE Transactions on Wireless Communications, vol. 19, No. 5, May 2020, 12 pages. [cited by applicant]
Yang et al., “Federated Learning via Over-the-Air Computation,” IEEE Trans. Wireless Commun., vol. 19, pp. 2022-2035, Mar. 2020, 14 pages. [cited by applicant]
Liu et al., “Privacy for Free: Wireless Federated Learning via Uncoded Transmission With Adaptive Power Control,” IEEE Journal on Selected Areas in Communications, vol. 39, Issue 1, Jan. 2021, 16 pages. [cited by applicant]
Ge et al., “Escaping From Saddle Points—Online Stochastic Gradient for Tensor Decomposition,” JMLR: Workshop and Conference Proceedings, vol. 40:1-46, 2015, 46 pages. [cited by applicant]
Zhu et al., “One-Bit Over-the-Air Aggregation for Communication-Efficient Federated Edge Learning: Design and Convergence Analysis,” IEEE Transactions on Wireless Communications, vol. 20, No. 3, Mar. 2021, 16 pages. [cited by applicant]
Lin et al., “Deploying Federated Learning in Large-Scale Cellular Networks: Spatial Convergence Analysis,” arXiv:2103.06056v1 [cs.IT] Mar. 10, 2021, 30 pages. [cited by applicant]
Jin et al., “How to escape saddle points efficiently,” in Proc. Intl. Conf. Mach. Learning (ICML), pp. 1724-1732, 2017, 9 pages. [cited by applicant]
Mertikopoulos et al., “On the almost sure convergence of stochastic gradient descent in non-convex problems,” In Proc. Conf. Neural Inf. Process. Syst. (NIPS), pp. 1117-1128, 2020, 12 pages. [cited by applicant]
Bertsekas et al., “Neuro-Dynamic Programming,” Springer, Boston, MA, 2008, pp. 1-129, 143 pages. [cited by applicant]
First Office Action received for Chinese Patent Application Serial No. 202210575990.6 dated Dec. 11, 2024, 14 pages(Including English Translation). [cited by applicant]