为何不通过矩阵乘法实现矩阵的线性插值运算?
问题背景
我是一名正在学习线性代数的数学专业本科生,近期看到一则新闻中的诉讼案件,以视频证据放大时经过插值运算生成了新像素为由驳回了相关证据,这让我开始思考应当如何对矩阵进行线性插值。
查阅相关资料后我发现,现有相关算法大多采用嵌套for循环实现,几乎没有用到线性代数相关方法,这令我很意外,我原本认为矩阵乘法这类运算的效率会更高。
最终我找到了一种更简单、也更符合直觉的方法,可以通过线性代数实现矩阵的最近邻插值和线性插值:假设我们有一个m×n的矩阵A,只需构造两个简单矩阵:维度为(2m-1)×m的矩阵L,以及维度为n×(2n-1)的矩阵R,通过运算L * A * R就能得到维度为(2m-1)×(2n-1)、完成了行列插值的矩阵,L和R的构造过程简单易懂。
核心疑问
- 为什么程序员不使用矩阵乘法来做矩阵插值呢?
- 理论上和嵌套for循环的实现相比,显卡是不是能让这类计算的速度提升很多?
- 还是说程序员已经在这么做了,只是因为方法过于基础所以没有太多公开资料?
补充说明
我之前提到的「用嵌套循环而非矩阵乘法」的表述不够严谨,导致了很多误解:我并不是说GPU不会执行循环操作,只是指这部分逻辑会被封装在库或者GPU底层逻辑中,优秀的软件都会做这类函数封装。而且直接用嵌套循环编程的话就没法利用矩阵数学算法或者GPU带来的优化。
矩阵乘积的算法是否使用嵌套for循环其实无关紧要,它可能用递归函数实现,也可能用类似DOOM游戏中求逆平方的高效反直觉技巧实现,这点本身并不重要,这个小歧义导致大部分讨论偏离了主题是很可惜的。
已验证的结论
目前看来我的理解基本是正确的:GPU更适合处理矩阵运算,但仅针对超大规模矩阵生效。我的问题也已经得到了充分解答:FFT的速度远快于O(n^3)的矩阵乘法。
推荐查看@datenwolf的回答及相关评论了解更多细节。
内容的提问来源于stack exchange,提问作者Adam Neeley

