近似低秩矩阵的奇异值分解与求逆-粤港澳大湾区（黄埔）国际算法算例大赛

赛事一览

CONTEST PROCESS

近似低秩矩阵的奇异值分解与求逆已结束

报名参赛

报名开始时间 2022-08-06
报名结束时间 2022-10-07
总奖金池￥1000000

一：项目概况

1、大赛介绍：

数字经济时代，算法作为一种战略性科技要素已成为推进数字技术与实体经济深度融合的核心支撑。为发挥国家实验室作用，推动粤港澳大湾区大数据与人工智能算法生态体系建设，琶洲实验室（黄埔）受广州市黄埔区政府委托，自2022起创办《粤港澳大湾区（黄埔）国际算法算例大赛》（以下简称“大赛”），旨在打造大湾区首个以算法为主题的国际型竞赛，以此推动原始创新, 并带动数字经济的高质量发展。
大赛以当前数字技术发展趋势和现实应用需求为牵引，面向全国遴选优质算法、汇聚全球高精尖技术、招揽国际算法高端人才。大赛坚持以科学性、引领性、实用性为原则，聚焦大数据、人工智能、物联网、云计算、元宇宙等新一代数字技术和互联网+、智能+等数字经济场景。大赛采取每年聚焦不同主题的方式开展。首届算法大赛聚焦后深度学习时代AI 基础算法和智慧城市、智能制造等领域内的行业算法场景。

2、大赛赛程安排：

2022年7月20日-11月15日

07月20日10:00：开启预报名
08月06日10:00：初赛正式开启报名，下载数据集，线下开发
08月22日10:00：在【初赛A榜】开始提交比赛代码，主办方进行成绩评测
10月07日10:00：大赛截止报名
10月07日12:00：【初赛A榜】截止提交代码
10月08日10:00-10月09日12:00：【初赛B榜】提交比赛代码
10月9日-10月21日：主办方用新的测试集进行测试代码并进行代码审查
10月22日：【初赛B榜】结果宣布，根据B榜成绩前14名进入决赛阶段（擂台赛）
10月22日-11月1日：出题方提供决赛数据。任何一只决赛队伍均可申请成为新擂主，并提供数据集，主办方进行审核并统一发布
10月22日10:00-11月10日12:00：决赛团队下载数据集，并线下调试代码，到【决赛A榜】提交代码，评测组线下评测
11月10日12:00-11月11日12:00：决赛团队到【决赛B榜】提交最终代码
11月11日-11月17日：评测组进行评测及审核
11月底：决赛答辩

3、大赛参赛人员：

大赛面向全社会开放，个人、高等院校、科研单位、企业、创客团队等人员均可报名参赛；

每位选手仅能加入一支参赛队伍，每只队伍组队上限5人。

注：（1）大赛组织机构单位中除了擂台赛，涉及题目编写、数据接触的人员禁止参赛；

（2）主办方和竞赛制赛道出题方可参赛，不参与排名。

“关于组队”

您需要以团队为单位来参与竞赛，即便您是单人参赛也需要创建一支队伍。

组队详情：点击https://www.cvmart.net/document

4、报名须知：

1）在琶洲实验室（黄埔）官方活动页面进行报名参赛，后登录平台进行下载数据集，线下开发后提交代码；

2）确保报名信息真实有效，一经发现，将取消参赛资格及激励；

3）参赛必读手册：https://www.cvmart.net/community/detail/6631

4）大赛官方微信群，扫码加入社群，及时获取大赛信息

二、赛制设置

1、擂台制赛道介绍

擂台赛赛道瞄准解决国家重大需求的基础算法，聚焦后深度学习的人工智能及相关领域的核心问题，驱动人工智能及相关学科领域的关键技术发展。擂台制赛道由大赛组织方邀请领域内的顶尖专家教授作为赛题定义者，从学术前瞻性及未来人工智能相关学科的发展趋势出发，根据学术领域的研究与认知，设计具有科学性和前瞻性的赛题，面向全世界遴选优质算法，打造全球人工智能算法高地。
擂台制赛道分为初赛和决赛两个个阶段，擂主直接进入决赛。初赛由开发者下载数据集进行线下开发，决赛擂主将于入围14名选手共同进行开发，为体现赛事公平性，将统一征集相关赛题数据集，增加应用场景，进行决赛角逐。

2、赛题介绍

本赛题聚焦一类有特别重要意义的（近似）低秩矩阵奇异值分解（SVD）与求逆问题。给定一个 $( m×n )$ 复矩阵 $( A )$ ，它的奇异值 $( {σ_i } )$ 中有相当多部分等于或接近于零，并且其 $( n_0 )$ 个最大的奇异值 $( {σ_i } )$ 的能量占比远大于99%：
问题的困难性在于， A的秩和 $( n_0 )$ 并不已知，而且所计算出的前 $( n_0 )$ 个最大奇异值和奇异向量应具有较高的精度。在这样的约束下，我们希望设计尽可能快的矩阵SVD（近似SVD）与求逆算法。

3、赛题比赛规则

大赛分为初赛和决赛两个比赛环节。

- 线上初赛

初赛时间：2022年8月6日-10月21日

初赛形式：初赛分为AB榜

【初赛A榜】

参赛队伍下载数据集，在本地完成代码(.m格式)编写，调试平台可视情况选择Octave/Matlab之一，在赛题【结果提交】处上传代码压缩包。主办方将在统一的硬件和软件平台对各队伍代码进行执行，并统计运行时间，最终给出打分。

【初赛B榜】

所有参赛队伍开始提交最终代码，主办方采用新的数据集进行测评，筛选出前14名进行成绩审核，无作弊行为，进入决赛

- 线上决赛

决赛时间：2022年11月1日-11月15日

决赛形式：

【擂台赛】

决赛采取擂台赛的形式，首先由出题方（擂主）提供之前未公开、与初赛同类型的数据进行算法设计与评测，参赛队伍在该数据上进行测试并排位。同时，任何决赛参赛队伍均可申请成为新擂主，并发布相应的数据集进行擂台赛，所有队伍在新擂主发表的数据集上重新测试并进行排位。决赛队伍也可不申请成为擂主，仅参加别的擂主发布的数据赛题进行比赛评测。

【决赛A榜】

参赛队伍下载新的数据集，同【初赛A榜】

【决赛B榜】

参赛队伍根据【决赛A榜】的结果提交代码，主办方采用新的数据集进行测评，筛选出前8名进行成绩审核，无作弊行为，进入答辩环节。

注：初赛及决赛皆为线下评测委员会测试成绩，成绩一周更新一次，第一次提交模型后，成绩将展示为0，成绩评测完后排行榜会再继续更新

- 答辩环节：

决赛成绩前8名提交竞赛方法描述（PDF、PPT）评测委员会将根据参赛者的技术思路、理论深度、复赛实验效果进行综合评分。最终依据决赛评价标准，综合评选出最终的获奖队伍。

4、注意事项

本竞赛仅可使用比赛主办方与擂主提供的数据。
初赛完毕后即决出最终入围决赛排名。排名前14的队伍进入决赛。
若发现有队伍存在违规作弊行为，决赛名额以及最终排名依照综合性能指标顺延

违规作弊行为包括但不限于：

代码格式与赛题要求不符合
提交代码无法复现出评测结果
违规使用白名单外的函数及操作
其它存在违反本次比赛规则的行为

一、需求背景

1、项目背景及意义：

矩阵计算是信息处理最基础的计算任务，也是大数据计算公认的“七大巨人问题”之一。矩阵基础计算理论的每一次进步，都会对大数据分析、信息与通信等相关产业产生广泛的影响，引发一系列的技术变革，大幅促进生产力的发展。

开展针对近似低秩矩阵的奇异值分解（SVD）与求逆算法的研究，对信息处理、大数据基础理论的发展有重要贡献，可推动相关核心技术的革新。

二、赛题描述

对于给定的矩阵以及该矩阵非零奇异值个数所占比例的条件约束，本赛题要求参赛队开发快速高效的矩阵奇异值分解与求逆算法。

赛题共分为4个任务，以下描述任务设定：
任务1：给定非满秩复矩阵 $( A∈mathbb{C}^{m×n},(m≥n) )$ ，矩阵秩r已知，且r≤(n/2)，求矩阵A的奇异值分解。在满足精度要求的前提下，比拼运算时间，时间越少，得分越高。

任务2：给定非满秩复矩阵 $( A∈mathbb{C}^{m×n},(m≥n) )$ ，矩阵秩r未知，且r≤(n/2)，求矩阵A的奇异值分解。在满足精度要求的前提下，比拼运算时间，时间越少，得分越高。
任务3：给定满秩复矩阵 $( A∈mathbb{C}^{m×n},(m≥n) )$ ，其中A的前p个奇异值满足：

$( frac{(∑_{i=1}^p {σ}_i^2 )}{∑_{j=p+1}^n {σ}_j^2 }≥10^{10}，且p≤frac{n}{2} )$ 。

求矩阵A的近似奇异值分解。在满足精度要求的情况下，比拼运算时间，时间越少，得分越高。

只要满足精度即可，无需计算所有奇异向量和奇异值。

任务4：给定非满秩复矩阵 $( A∈mathbb{C}^{m×n},(m≥n) )$ ，矩阵秩r未知，且r≤(n/2)，求 $( (I+AA^H ) )$ 的逆矩阵。在满足精度要求的前提下，比拼运算时间，时间越少，得分越高。

初赛与决赛任务相同，共提供四批数据集，【初赛A榜】数据集，【初赛B榜】数据集（不可下载）、【决赛A榜】数据集，【决赛B榜】数据集（不可下载），数据集产生准则见数据集说明，每个任务的打分规则见评测标准。

三、数据集说明

数据集1，对应任务1，包含3组矩阵集，其中 $( A_{256×128} )$ 200个， $( A_{512×256} )$ 200个， $( A_{1024×512} )$ 200个，并且提供每个矩阵的秩，矩阵的秩在[n/8,…, n/2]中随机均匀取值。
数据集2，对应任务2，包含3组矩阵集，其中 $( A_{256×128} )$ 200个， $( A_{512×256} )$ 200个， $( A_{1024×512} )$ 200个，矩阵的秩在[n/8,…, n/2]中随机均匀取值。
数据集3，对应任务3，包含3组矩阵集，其中 $( A_{256×128} )$ 200个， $( A_{512×256} )$ 200个， $( A_{1024×512} )$ 200个 $( sum_{i=1}^{p} sigma_{i}^{2} / sum_{i=p+1}^{n} sigma_{j}^{2} geq 10^{10} )$ ，其中p在[n/8,…, n/2]中随机均匀取值。
提供的数据集已按照最大奇异值归一，即 $( σ ̃_i=σ_i /σ_{max} )$ ，归一后奇异值范围为[0,1]。
数据集4，对应任务4，包含3组矩阵集，其中 $( A_{256×128} )$ 200个， $( A_{512×256} )$ 200个， $( A_{1024×512} )$ 200个，其中r在[n/8,…, n/2]中随机均匀取值。

注：以上【数据集1-4】中的矩阵均为稠密阵。

四、提交结果

【初赛A榜】

提交形式：将4个任务代码打包成zip包进行上传，zip压缩包命名：注册团队名；
提交次数：每周1次
开始提交时间：8月22日
提交内容：其中包含4个.m文件，分别对应任务1到任务4的执行代码；提交数据的需要提供运行说明文档，依赖安装脚本，及提供相关的全部代码。

【初赛B榜】

提交形式及内容：同初赛A榜，所有参赛队伍提交最终比赛代码
提交次数：1次
提交时间：10月08日10:00-10月09日12:00
【决赛A榜】
同初赛A榜
提交次数：每周2次
【决赛B榜】
同初赛B榜
提交次数：1次

任务1:

文件命名： my_svd_1.m
函数命名及接口：function [u,s,v] = my_svd_1(A , r)
变量说明： A为输入矩阵，维度为m*n，m,n为A矩阵的行数和列数。例如对于数据集1中的 $( A_{512×256} )$ ，m=512，n=256, r是矩阵A的秩。 u,s,v为矩阵A的左奇异向量矩阵，奇异值矩阵，右奇异向量矩阵的估计量。矩阵的误差定义为：

e=norm(A-u*s*v’ , ‘fro’ ) / norm(A , ‘fro’ )

任务2:

文件命名： my_svd_2.m
函数命名及接口：function [u,s,v] = my_svd_2(A)
变量说明：同任务1

任务3:

文件命名： my_svd_3.m
函数命名及接口：function [u,s,v] = my_svd_3(A)
变量说明：同任务1

任务4:

文件命名： my_inverse.m
函数命名及接口：function [inv_AA] = my_inverse (A)
变量说明： A同任务1, inv_AA为 $( (I+AA^H ) )$ 求逆计算结果，维度为m*m。

五、评测标准

SVD精度要求（任务1，任务2，任务3）：

算法运行结束后，产生A的左奇异向量矩阵U、奇异值矩阵S、右奇异向量矩阵V，定义 $( bar{A} =USV^H )$ 为A的近似奇异值分解（奇异值分解）。

定义近似奇异值分解的误差为，给定误差 $( ε )$ ，要求 $( E_1<ε )$ 。

定义左、右奇异向量矩阵U、V的正交性误差为

$( G_{1}=max left{frac{left|I u-U^{H} Uright|_{F}}{|I u|_{F}}, frac{left|I v-V^{H} Vright|_{F}}{|I v|_{F}}right} )$ ，其中 $( Iu )$ 和 $( Iv )$ 为单位向量。

给定误差 $( δ )$ , 要求 $( G_1<δ )$ 。

矩阵求逆精度要求（任务4）：设所求的矩阵 $( (I+AA^H ) )$ 的逆矩阵为B，则定义误差:

$( E_2=frac{‖(I+AA^H )*B-I‖_F}{sqrt{m} } )$

给定误差 $( ε, )$ 要求 $( E_1<ε )$

注： $( []^H )$ 为共轭转置。

评审指标	指标说明	分数
1、低秩矩阵奇异值分解（秩已知）	精度：要求数据集中的每个矩阵 $( E_1 )$ 值小于 $( 10^{-12} )$ ，要求U，V正交性校性误差 $( G_1 )$ 小于 $( 10^{-12} )$ ；评分： $( E_1 )$ 与 $( G_1 )$ 任意一个不满足精度要求，该矩阵得分为S=0. 在满足精度前提下，对于数据集中的每个矩阵基于参赛队伍运行时间降序排列，最短时间队伍该矩阵得分S=T（T大于等于队伍数），其次S-1分，依次类推，该任务数据集中所有矩阵的分数累加得分Q为该任务的初始分，基于如下方式计算该任务得分：Q/（M3）(10/T)，其中M为评测方选择的该任务中每个维度的矩阵数量。	10分
2、低秩矩阵奇异值分解（秩未知）	精度：要求数据集中的每个矩阵 $( E_1 )$ 值小于 $( 10^{-12} )$ ，要求U，V正交性校性误差 $( G_1 )$ 小于 $( 10^{-12} )$ ；评分： $( E_1 )$ 与 $( G_1 )$ 任意一个不满足精度要求，该矩阵得分为S=0.. 在满足精度前提下，对于数据集中的每个矩阵基于参赛队伍运行时间降序排列，最短时间队伍该矩阵得分S=T（T大于等于队伍数），其次S-1分，依次类推，该任务数据集中所有矩阵的分数累加得分Q为该任务的初始分，基于如下方式计算该任务得分：Q/（M3）(20/T)，其中M为评测方选择的该任务中每个维度的矩阵数量。	20分
3、近似低秩矩阵奇异值分解	精度：要求数据集中的每个矩阵 $( E_1 )$ 值小于 $( 10^{-5} )$ ，要求U，V正交性校性误差 $( G_1 )$ 小于 $( 10^{-12} )$ ；评分： $( E_1 )$ 与 $( G_1 )$ 任意一个不满足精度要求，该矩阵得分为S=0.. 时间：在满足精度前提下，对于数据集中的每个矩阵基于参赛队伍运行时间降序排列，最短时间队伍该矩阵得分S=T（T大于等于队伍数），其次S-1分，依次类推，该任务数据集中所有矩阵的分数累加得分Q为该任务的初始分，基于如下方式计算该任务得分：Q/（M3）(10/T)，其中M为评测方选择的该任务中每个维度的矩阵数量。	10分
4矩阵求逆	精度：要求数据集中的每个矩阵 $( E_1 )$ 值小于 $( 10^{-12} )$ ；评分： $( E_2)$ 不满足精度要求，该矩阵得分S=0 时间：在满足精度前提下，对于数据集中的每个矩阵基于参赛队伍运行时间降序排列，最短时间队伍该矩阵得分S=T（T大于等于队伍数），其次S-1分，依次类推，该任务数据集中所有矩阵的分数累加得分Q为该任务的初始分，基于如下方式计算该任务得分：Q/（M3）(20/T)，其中M为评测方选择的该任务中每个维度的矩阵数量。	20分
答辩得分	进入决赛的15支队伍最终选择前8名进行答辩，就提出算法的技术思路、理论创新度、决赛实验效果进行解释，评委就此进行打分，满分40分。	40分
总分	各任务的最终分累加作为比赛总分	100分

六、比赛规则

考虑参赛队伍来自于不同的学科领域，本赛题的主旨在于比拼矩阵奇异值分解及求逆的基础算法设计，希望参赛队伍的共同目标是设计低复杂度的算法，为了最大程度避免验证平台底层实现对算法评估的影响，(例如商用科学计算软件底层优化导致了低时间复杂度矩阵乘法有时无法在运算时间上体现出优势)，现对代码编写规范做以下要求：

参赛队伍在本地完成代码(.m格式)编写，调试平台可视情况选择Octave/Matlab之一。主办方将在统一的硬件和软件平台对各队伍代码进行执行，并统计运行时间，最终给出打分。
函数及操作白名单（终版）：只能使用基础运算操作函数，可使用的有： →标量操作：标量加法、标量减法、标量乘法、标量除法、标量乘方、sqrt、标量三角函数、求模（abs）、求余、round、floor、fix、sign； →矩阵（向量）操作：矩阵加法、矩阵减法、矩阵取相反数、求F范数、(共轭)转置、矩阵截取与拼接（A(a:b,c:d)，diag，tril，triu，[A,B]，[A;B]，cell2mat）、size函数、求最大最小排序（min，max，sort）、find、isempty、randsample、reshape、repmat，real，imag，conj； →特殊矩阵构造函数：随机数生成函数（unifrnd，randn，rand，randi，randperm）、eye、ones、zeros、complex； →逻辑索引，global关键字，if语句中的逻辑判断符（|| &&）。
不能采用其他加速的方法，比如混编（MEX）、调用C库、GPU、多核多线程并行等加速操作方法
运算时间只统计各队伍矩阵运算函数的运算时间，数据读取，精度检验不计入时间。

各队伍需要在初赛，决赛代码提交截止时间在组委会指定的链接上传代码，到达代码提交截止时间后，将关闭本阶段比赛的代码上传通道，由评委会审视各队伍代码是否满足上述规定，对于代码审视不合格的队伍将直接取消比赛资格，并从后续代码合规队伍中按照排名向上递补。