CIF: Small: Secure and Fast Federated Low-Rank Recovery from Few Column-wise Linear, or Quadratic, Projections

CIF：小型：通过少量列线性或二次投影进行安全快速的联合低秩恢复

基本信息

批准号：
2115200
负责人：
Namrata Vaswani
金额：
$ 56.45万
依托单位：
Iowa State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-07-01 至 2025-06-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2115200&HistoricalAwards=false
关键词：
CIF Small Secure Fast Federated

项目摘要

Large-scale usage of Internet-of-Things (IoT) devices, smartphones and surveillance cameras has resulted in huge amounts of geographically distributed data in current times. This naturally leads to questions of algorithm design for efficient processing and inference on this data. There is a need to compress (sketch) this data before it can be stored, processed, or transmitted. At the other extreme, in projection-imaging settings, such as magnetic resonance imaging (MRI), computed tomography (CT), Fourier ptychography, or sub-diffraction imaging, data is acquired one sample at a time, making the process very slow. In this scenario as well, data may be distributed, e.g., for a jointly reconstructed functional MR images of different human subjects, with scans that may have been acquired at different hospitals around the country. In many of these settings, privacy concerns dictate that the acquired measurements need to be processed in a federated manner. Moreover, the distributed nature of the data necessitates the design of secure approaches that are robust to attacks by potentially malicious nodes. Both efficient sketching and fast dynamic projection imaging require the ability to recover the true signal or image sequence from highly undersampled measurements. Since the early work on compressed sensing (CS), sparsity and structured sparsity assumptions have been exploited very fruitfully for both type of problems. However, there is limited literature on the use of the low-rank (LR) assumption on signal sequences, and almost none that theoretically analyzes the resulting approaches. This project develops fast, sample-efficient, and federated (private and communication-efficient) algorithms for provably correct subspace learning and low-rank matrix recovery from few column-wise independent linear, or quadratic projections. Extensions to LR plus sparse (LR+S) recovery are also examined. It should be noted that this problem setting is very different from other well-investigated LR recovery problems such as multivariate regression (due to the use of different independent measurement matrices for each signal), LR matrix sensing, or LR matrix completion. The team is investigating the design of Gradient Descent (GD) based solutions that are guaranteed, with high probability, to recover an n x q rank-r matrix from m independent linear projections of each of its q columns with m just large enough to satisfy mq C (n+q) r^2 approximately, and that converge geometrically to the true matrix. Furthermore, this project designs novel secure algorithms that are robust to Byzantine nodes for the above classes of problems. This effort is expected to lead to newer solution approaches and analysis techniques, since commonly used assumptions such as strongly convex cost functions and i.i.d. measurements do not hold in this setting. Finally, this project partially supports the new CyMathKids initiative, whose goal is to provide sustained year-long support and extension in Mathematics to grade-school students from under-funded school districts in Des Moines, Iowa. It is intended to fill some of the academic achievement gaps between disadvantaged students and advantaged ones, and do so while the gaps are still small: the pilot phase focuses on elementary students with a plan to follow the same students through the school years.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

当前，物联网（IoT）设备、智能手机和监控摄像头的大规模使用产生了大量地理分布的数据。这自然会导致算法设计问题，以便有效处理和推断这些数据。在存储、处理或传输这些数据之前，需要对其进行压缩（草图）。另一方面，在投影成像环境中，例如磁共振成像 (MRI)、计算机断层扫描 (CT)、傅里叶叠层成像或亚衍射成像，一次采集一个样本的数据，使得过程非常缓慢。同样在这种情况下，数据也可以被分发，例如，针对不同人类受试者的联合重建的功能MR图像，以及可能在全国各地的不同医院获取的扫描。在许多这样的设置中，隐私问题表明需要以联合方式处理所获取的测量结果。此外，数据的分布式特性需要设计能够抵御潜在恶意节点攻击的安全方法。高效的草图绘制和快速动态投影成像都需要能够从高度欠采样的测量中恢复真实信号或图像序列。自从压缩感知（CS）的早期工作以来，稀疏性和结构化稀疏性假设已经在这两类问题上得到了非常有效的利用。然而，关于在信号序列上使用低秩（LR）假设的文献有限，并且几乎没有对所得方法进行理论上分析的文献。该项目开发快速、样本高效和联合（私有和通信高效）算法，用于可证明正确的子空间学习和从少数列独立线性或二次投影中恢复低秩矩阵。还研究了 LR 加稀疏 (LR+S) 恢复的扩展。应该注意的是，这个问题设置与其他经过深入研究的 LR 恢复问题有很大不同，例如多元回归（由于对每个信号使用不同的独立测量矩阵）、LR 矩阵传感或 LR 矩阵完成。该团队正在研究基于梯度下降 (GD) 的解决方案的设计，该解决方案保证以高概率从每个 q 列的 m 个独立线性投影中恢复 n x q 秩-r 矩阵，其中 m 刚好足够满足 mq C (n+q) r^2 近似，并且几何收敛于真实矩阵。此外，该项目设计了新颖的安全算法，对于上述类别的问题对拜占庭节点具有鲁棒性。这项工作预计将带来更新的解决方案和分析技术，因为常用的假设（例如强凸成本函数和 i.i.d.）测量值在此设置下不成立。最后，该项目部分支持新的 CyMathKids 计划，其目标是为爱荷华州得梅因市资金不足学区的小学生提供持续一年的数学支持和扩展。它的目的是填补弱势学生和优势学生之间的一些学业成绩差距，并在差距仍然很小的时候这样做：试点阶段的重点是小学生，计划在整个学年中跟踪相同的学生。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Distributed Matrix Computations With Low-Weight Encodings

具有低权重编码的分布式矩阵计算

DOI：
10.1109/jsait.2023.3308768
发表时间：
2023-01
期刊：
IEEE Journal on Selected Areas in Information Theory
影响因子：
0
作者：
Das, Anindya Bijoy;Ramamoorthy, Aditya;Love, David J.;Brinton, Christopher G.
通讯作者：
Brinton, Christopher G.

A Unified Treatment of Partial Stragglers and Sparse Matrices in Coded Matrix Computation

编码矩阵计算中部分散乱矩阵和稀疏矩阵的统一处理

DOI：
10.1109/jsait.2022.3186908
发表时间：
2022-06
期刊：
IEEE Journal on Selected Areas in Information Theory
影响因子：
0
作者：
Das, Anindya Bijoy;Ramamoorthy, Aditya
通讯作者：
Ramamoorthy, Aditya

Distributed Matrix Computations with Low-weight Encodings

使用低权重编码的分布式矩阵计算

DOI：
10.1109/isit54713.2023.10206445
发表时间：
2023-06
期刊：
IEEE
影响因子：
0
作者：
Das, Anindya Bijoy;Ramamoorthy, Aditya;Love, David J.;Brinton, Christopher G.
通讯作者：
Brinton, Christopher G.

Fully Decentralized and Federated Low Rank Compressive Sensing

完全分散和联合的低阶压缩感知