Data Shuffling in Wireless Distributed Computing via Low-Rank Optimization
Open accessThe DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Abstract
Intelligent mobile platforms such as smart vehicles and drones have recently become the focus of attention for onboard deployment of machine learning mechanisms to enable low latency decisions with low risk of privacy breach. However, most such machine learning algorithms are both computation-and-memory intensive, which makes it highly difficult to implement the requisite computations on a single device of limited computation, memory, and energy resources. Wireless distributed computing presents new opportunities by pooling the computation and storage resources among devices. For low-latency applications, the key bottleneck lies in the exchange of intermediate results among mobile devices for data shuffling. To improve communication efficiency, we propose a co-channel communication model and design transceivers by exploiting the locally computed intermediate values as side information. A low-rank optimization model is proposed to maximize the achieved degrees-of-freedom (DoF) by establishing the interference alignment condition for data shuffling. Unfortunately, existing approaches to approximate the rank function fail to yield satisfactory performance due to the poor structure in the formulated low-rank optimization problem. In this paper, we develop an efficient difference-of-convex-functions (DC) algorithm to solve the presented low-rank optimization problem by proposing a novel DC representation for the rank function. Numerical experiments demonstrate that the proposed DC approach can significantly improve the communication efficiency whereas the achievable DoF almost remains unchanged when the number of mobile devices grows.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“A low-rank matrix optimization based transceiver design approach was proposed in [52] for fast shuffling intermediate values in wireless distributed computing, thereby reducing the latency for horizontal edge inference via edge devices collaboration.”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [52]
Experimental — accuracy not yet measuredIn the citing paper
“This issue was addressed by a difference-of-convex-functions (DC) programme [31], [52], [99] by representing the rank function via an equivalent DC function.”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [52]
In the citing paper
“Most of the resource allocation problems in edge AI need to solve a series of nonconvex optimization problems, e.g., nonconvex sparse optimization for device selection in wireless FL, nonconvex quadratic programming for transceiver design in over-the-air FL [31], lowrank matrix optimization for interference management in edge device distributed inference [52], and unit modulus constrained phase”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [52]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476 · cited 5×
“The authors of [7] exploited the coded multicast opportunities by proposing a coded scheme called “Coded MapReduce” to reduce the communication load for data shuffling in wireline distributed computing framework.”
MethodInfluentialHan, S., Mao, H., & Dally, W. J. (2015) · arXiv · doi:10.48550/arxiv.1510.00149 · Cited by 4,662 · cited 3×
“However, the ultra-low latency requirement [2] for executing intensive computation tasks of mobile edge intelligence applications imposes an unrealistic burden on the computational capability of resource-constrained mobile devices [3] and ranks as one of the key challenges.”
BackgroundEfficient Processing of Deep Neural Networks: A Tutorial and Survey
Sze, V., Chen, Y.-H., Yang, T.-J., & Emer, J. S. (2017) · Proceedings of the IEEE · doi:10.1109/jproc.2017.2761740 · Cited by 4,215
Interference Alignment and Degrees of Freedom of the $K$-User Interference Channel
Cadambe, V. R., & Jafar, S. A. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.926344 · Cited by 2,970 · cited 4×
“y I 1(s l) = X i:l2T i U kl(H ki I r)V ils l; I 2(fs j: j2T kg) = X j2T k X i:j2T i U kl(H ki I r)V ijs j; I 3(fs j: j=2T k[flgg) = X j= 2T k[flg X i:j i U kl(H ki I r)V ijs j: Interference alignment [8] turns out to be a powerful tool to handle the mutual interference among users. The basic idea is to make signals re…”
BackgroundMethodInfluentialElements of Information Theory
Nalewajski, R. F. (2011) · Perspectives in Electronic Structure Theory · doi:10.1007/978-3-642-20180-6_8 · Cited by 2,309
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training
Lin, Y., Han, S., Mao, H., Wang, Y., & Dally, W. J. (2017) · arXiv · doi:10.48550/arxiv.1712.01887 · Cited by 1,134 · cited 1×
“In wireless distributed computing systems, communication often becomes the key bottleneck [4] [14] to accomplish the computation tasks.”
BackgroundCheng, Y., Wang, D., Zhou, P., & Zhang, T. (2018) · IEEE Signal Processing Magazine · doi:10.1109/msp.2017.2765695 · Cited by 817 · cited 1×
“Storage size is often one of the key limiting factors in a single device when deploying deep learning model [3], [5].”
BackgroundDeepTrust^RT: Confidential Deep Neural Inference Meets Real-Time!
Babar, M. F., & Hasan, M. (2024) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ecrts.2024.13 · Cited by 708
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding
O’Donoghue, B., Chu, E., Parikh, N., & Boyd, S. (2016) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-016-0892-3 · Cited by 664 · cited 2×
“The first-order alternating direction method of multipliers (ADMM) [20], [21] significantly reduces the computational cost to O ( SD 2 + D 3 ) for each iteration (please refer to IV-D for more details).”
MethodA Fundamental Tradeoff Between Computation and Communication in Distributed Computing
Li, S., Maddah-Ali, M. A., Yu, Q., & Avestimehr, A. S. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756959 · Cited by 451
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439 · cited 4×
“Low-rank approaches have attracted enormous attention in machine learning, high-dimensional statistics, and recommendation system [9].”
BackgroundInfluentialIterative reweighted algorithms for matrix rank minimization
Mohan, K., & Fazel, M. (2012) · Journal of Machine Learning Research · doi:10.5555/2503308.2503351 · Cited by 395 · cited 4×
“To further improve the performance of nuclear norm relaxation and enhance low-rankness, the iterative reweighted least square algorithm IRLS-p [10] ( 0 ≤ p ≤ 1 ) is proposed by alternating between minimizing weighted Frobenius norm and updating weights.”
MethodInfluentialCharacterization of the subdifferential of some matrix norms
Watson, G. A. (1992) · Linear Algebra and its Applications · doi:10.1016/0024-3795(92)90407-2 · Cited by 364 · cited 1×
“The subgradient of ||| σ ( X ) ||| 2 k, 2 with respect to σ ( X ) is given by According to the subdifferential of orthogonally invariant norm [26], we obtain (64) It then follows that where Σ k is given by Note that each iteration of (59) and (60) for the proposed DC algorithm can be computed much…”
DC programming and DCA: thirty years of developments
Le Thi, H. A., & Pham Dinh, T. (2018) · Mathematical Programming · doi:10.1007/s10107-018-1235-y · Cited by 348 · cited 2×
“Due to the nonconvex DC objective function, the majorization-minimization (MM) algorithm [11], [12] can be adopted to iteratively solve a convex subproblem by linearizing ||| X ||| k as Tr ( ∂ ||| X t ||| H k X ) , i.e., by solving minimize in the ( t + 1) -th iteration.”
BackgroundMethodDC formulations and algorithms for sparse optimization problems
Gotoh, J.-Y., Takeda, A., & Tono, K. (2018) · Mathematical Programming · doi:10.1007/s10107-017-1181-0 · Cited by 184 · cited 4×
“Recently, a DC (difference-of-convex-functions) [11], [12] representation of the rank function has been proposed in [13] with demonstrated effectiveness.”
BackgroundMethodInfluentialIndex Coding—An Interference Alignment Perspective
Maleki, H., Cadambe, V. R., & Jafar, S. A. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2338865 · Cited by 143
A Scalable Framework for Wireless Distributed Computing
Li, S., Yu, Q., Maddah-Ali, M. A., & Avestimehr, A. S. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2017.2702605 · Cited by 130 · cited 5×
“In wireless distributed computing systems, communication often becomes the key bottleneck [4] [14] to accomplish the computation tasks.”
BackgroundMethodInfluentialFeasibility of Interference Alignment for the MIMO Interference Channel
Bresler, G., Cartwright, D., & Tse, D. N. C. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2338857 · Cited by 124 · cited 1×
“As a first-order characterization of channel capacity, degree-of-freedom (DoF) analysis and optimization are widely applied in interference channels [8], [16], [17].”
MethodLarge-Scale Convex Optimization for Dense Wireless Cooperative Networks
Shi, Y., Zhang, J., O'Donoghue, B., & Letaief, K. B. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2443731 · Cited by 118
Self-citationAdaptive Learning in Complex Reproducing Kernel Hilbert Spaces Employing Wirtinger's Subgradients
Bouboulis, P., Slavakis, K., & Theodoridis, S. (2012) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2011.2179810 · Cited by 73 · cited 2×
“The conjugate function is defined by where the inner product is defined as (cid:104) X , Y (cid:105) = Tr ( X H Y ) based on [24].”
BackgroundMethodLow-Rank Matrix Completion for Topological Interference Management by Riemannian Pursuit
Shi, Y., Zhang, J., & Letaief, K. B. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2544758 · Cited by 56
Self-citationOn matrix approximation problems with Ky Fank norms
Watson, G. A. (1993) · Numerical Algorithms · doi:10.1007/bf02210386 · Cited by 33 · cited 2×
“Tr(@jjjX tjjjH k X), i.e., by solving minimize X2CD D kXk k Tr(@jjjX tjjjHX) subject to A(X) = b (44) in the (t+ 1)-th iteration. Here X t is the solution to (44) in the t-th iteration. @jjjX tjjj k [22] denotes the subdifferential of jjjXjjj k at X t and can be chosen as @jjjX tjjj k= fUdiag(q)VH;q= [1; ;1 | {z } k ;…”
MethodFinding the Largest Low-Rank Clusters With Ky Fan $2$-$k$-Norm and $\ell_1$-Norm
Doan, X. V., & Vavasis, S. A. (2016) · SIAM Journal on Optimization · doi:10.1137/140962097 · Cited by 25 · cited 2×
“We first introduce: Definition 2: For any integer 1 ≤ k ≤ min{m,n}, the Ky Fan 2-k norm [23] of matrix X ∈ Cm×n is defined as the 2norm of the subvector formed by the largest-k singular values of X .”
BackgroundMethodLow-Rank Optimization for Data Shuffling in Wireless Distributed Computing
Yang, K., Shi, Y., & Ding, Z. J. (2018) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2018.8461817 · Cited by 9 · cited 6×
“H k = H up k [1, 1] · · · H up k [1, L] .”
InfluentialSelf-citation
Research works printed but not linked: 2
- [11] P. D. Tao and L. T. H. An, 'Convex analysis approach to DC programming: Theory, algorithms and applications,' Acta Mathematica Vietnamica , vol. 22, no. 1, pp. 289-355, 1997. -
- [25] R. T. Rockafellar, Convex analysis . Princeton university press, 2015. -
Cited by
The Roadmap to 6G: AI Empowered Wireless Networks
Letaief, K. B., Chen, W., Shi, Y., Zhang, J., & Zhang, Y.-J. A. (2019) · IEEE Communications Magazine · doi:10.1109/mcom.2019.1900271 · Cited by 2,207
“A joint optimization of the uplink and downlink communication strategy was thus developed in [12] for shuffling the locally computed intermediate values across mobile devices.”
Self-citationEdge artificial intelligence for 6g: vision, enabling technologies, and applications
Letaief, K. B., Shi, Y., Lu, J., & Lu, J. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126076 · Cited by 829
“further improve the spectral efficiency, instead of reducing the volume of communication bits [221], a joint uplink and downlink design approach based on the interference alignment principle was developed in [52] to improve the communication data rates for local intermediate values shuffling.”
MethodInfluentialSelf-citationCommunication-efficient edge ai: algorithms and systems
Shi, Y., Yang, K., Jiang, T., Zhang, J., & Letaief, K. B. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.3007787 · Cited by 488
“Interestingly, coding technique plays a critical role in scalable data shuffling [31], [141] as well as straggler mitigation [145].”
BackgroundMethodInfluentialSelf-citationZhou, Y., Liu, L., Wang, L., Hui, N., Cui, X., Wu, J., Peng, Y., Qi, Y., & Xing, C. (2020) · Digital Communications and Networks · doi:10.1016/j.dcan.2020.05.003 · Cited by 238
“The same scenario in [36,37] designs a down-link and uplink MIMO transmission between users and the BS, which uses interference alignment to maximize the achievable degree of freedom and reduce the required transmission bandwidth.”
BackgroundIntelligent Reflecting Surface for Downlink Non-Orthogonal Multiple Access Networks
Fu, M., Zhou, Y., & Shi, Y. (2019) · 2019 IEEE Globecom Workshops (GC Wkshps) · doi:10.1109/gcwkshps45667.2019.9024675 · Cited by 199
“Specifically, we present an exact DC representation for the non-convex rank-one constrained positive semidefinite (PSD) matrix by exploiting the difference between the trace norm and the spectral norm [19].”
MethodSelf-citation
Metadata
- Authors
- Yang, K., Shi, Y., & Ding, Z.
- Affiliations
- University of Chinese Academy of Sciences (CN)
- ShanghaiTech University (CN)
- University of California, Davis (US)
- Venue
- IEEE Transactions on Signal Processing
- Published
- 2019-06-15
- Volume
- 67
- Issue
- 12
- Pages
- 3087-3099
- ISSN
- 1053-587X (ISSN-L)
- 1941-0476
- OpenAlex
- W2890278565
- Cited by
- 43
- References
- 24
- Citations by year
- 2026: 1 · 2025: 3 · 2024: 3 · 2023: 8 · 2022: 5 · 2021: 10 · 2020: 7 · 2019: 6
- FWCI
- 2.52
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- IEEE Transactions on Signal Processing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Natural Science Foundation of China (61601290)
- Shanghai Sailing Program (16YF1407700)
- National Science Foundation (CNS-1702752, ECCS1711823)
- Topics
- Physical Sciences › Engineering › Electrical and Electronic Engineering › Advanced MIMO Systems Optimization
- Physical Sciences › Computer Science › Computer Networks and Communications › IoT and Edge/Fog Computing
- Physical Sciences › Computer Science › Computer Networks and Communications › Cooperative Communication and Network Coding
- Keywords
- data shuffling, low-rank optimization, difference of convex functions, interference alignment, degrees of freedom, side information, communication efficiency, onboard machine learning, mobile devices
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.