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

物联网(IoT)设备、智能手机和监控摄像头的大规模使用导致了当今时代海量的地理分布数据。这自然导致了对这些数据进行有效处理和推断的算法设计问题。在可以存储、处理或传输该数据之前，需要对其进行压缩(草绘)。在另一种极端情况下，在诸如磁共振成像(MRI)、计算机层析成像(CT)、傅立叶层析成像或次衍射成像等投影成像设置中，数据是一次采集一个样本，使得该过程非常缓慢。同样在该场景中，可以利用可能已经在全国不同医院获取的扫描来分发数据，例如用于不同人类对象的联合重建的功能性MR图像。在许多这样的设置中，出于隐私考虑，需要以联合方式处理所获取的测量结果。此外，数据的分布式性质要求设计安全的方法，使其对潜在恶意节点的攻击具有健壮性。高效的草图绘制和快速动态投影成像都需要从高度欠采样的测量中恢复真实信号或图像序列的能力。自从压缩感知(CS)的早期工作以来，稀疏性和结构化稀疏性假设在这两类问题上都得到了非常有效的利用。然而，关于低阶假设在信号序列上的应用的文献有限，几乎没有从理论上分析由此产生的方法的文献。该项目开发了快速、样本高效和联合(私有和通信高效)算法，用于可证明正确的子空间学习和从几个列独立的线性或二次投影恢复低阶矩阵。对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.