2024/04/22 by Ali Khalesi, Khalesi, Ali, Petros Elia +1
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2404.14203
openalex publication_date 2024/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The work considers the N-server distributed computing scenario with K users requesting functions that are linearly-decomposable over an arbitrary basis of L real (potentially non-linear) subfunctions. In our problem, the aim is for each user to receive their function outputs, allowing for reduced reconstruction error (distortion) ε, reduced computing cost (γ; the fraction of subfunctions each server must compute), and reduced communication cost (δ; the fraction of users each server must connect to). For any given set of K requested functions -- which is here represented by a coefficient matrix \mathbf F ∈ ℝK × L -- our problem is made equivalent to the open problem of sparse matrix factorization that seeks -- for a given parameter T, representing the number of shots for each server -- to minimize the reconstruction distortion (1)/(KL)‖\mathbf F - DE‖2F overall δ-sparse and γ-sparse matrices D∈ ℝK × NT and E ∈ ℝNT × L. With these matrices respectively defining which servers compute each subfunction, and which users connect to each server, we here design our D,E by designing tessellated-based and SVD-based fixed support matrix factorization methods that first split F into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of D and E.