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

物联网（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的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.