  In this work we develop a fully decentralized, federated, and fast solution
to the recently studied Low Rank Compressive Sensing (LRCS) problem: recover an
nxq low-rank matrix from column-wise linear projections. An important
application where this problem occurs, and a decentralized solution is
desirable is in federated sketching: efficiently compressing the vast amounts
of distributed images/videos generated by smartphones and various other devices
while respecting the users' privacy. Images from different devices, once
grouped by category, are similar and hence the matrix formed by the vectorized
images of a certain category is well-modeled as being low rank. Suppose there
are p nodes (say p smartphones), and each store a subset of the sketches of its
images. We develop a decentralized projected gradient descent (GD) based
approach to jointly reconstruct the images of all the phones/users from their
respective stored sketches. The algorithm is such that the phones/users never
share their raw data but only summaries of this data with the other phones at
each algorithm iteration. Also, the reconstructed images of user g are obtained
only locally. Other users cannot reconstruct them. Only the column span of the
matrix is reconstructed globally. By "decentralized" we mean that there is no
central node to which all nodes are connected and thus the only way to
aggregate the summaries from the various nodes is by use of an iterative
consensus algorithm that eventually provides an estimate of the aggregate at
each node, as long as the network is strongly connected. We validated the
effectiveness of our algorithm via extensive simulation experiments.
