Sherman-Morrison-Woodbury formula 证明

2024-05-09 01:36

本文主要是介绍Sherman-Morrison-Woodbury formula 证明,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 公式
  • 2. 证明

1. 公式

M = I − u v T ⇒ M − 1 = I + u v T 1 − v T u (1) M=I-uv^T\Rightarrow M^{-1}=I+\frac{uv^T}{1-v^Tu}\tag{1} M=IuvTM1=I+1vTuuvT(1)

2. 证明

  • 定义矩阵E表示如下:
    E = [ I u v T 1 ] , D = 1 − v T u (2) E=\begin{bmatrix}I&&u\\\\v^T&&1\end{bmatrix},D=1-v^Tu\tag{2} E= IvTu1 ,D=1vTu(2)
    我们想求 E − 1 E^{-1} E1,可以通过增广矩阵,进行行变换得到,
  • 第一种方法是:将第一行乘以 v T v^T vT后加到第二行中.
    [ I 0 − v T 1 ] E = [ I u 0 D ] (3) \begin{bmatrix}I&&0\\\\-v^T&&1\end{bmatrix}E=\begin{bmatrix}I&&u\\\\0&&D\end{bmatrix}\tag{3} IvT01 E= I0uD (3)
    E − 1 = [ I u 0 D ] − 1 [ I 0 − v T 1 ] = [ I + u D − 1 v T − u D − 1 − D − 1 v T D − 1 ] (4) E^{-1}=\begin{bmatrix}I&&u\\\\0&&D\end{bmatrix}^{-1}\begin{bmatrix}I&&0\\\\-v^T&&1\end{bmatrix}=\begin{bmatrix}I+uD^{-1}v^T&&-uD^{-1}\\\\-D^{-1}v^T&&D^{-1}\end{bmatrix}\tag{4} E1= I0uD 1 IvT01 = I+uD1vTD1vTuD1D1 (4)
  • 第二种方法是:将第二行乘以 u u u后加到第一行中.
    [ I − u 0 1 ] E = [ I − u v T 0 v T 1 ] (5) \begin{bmatrix}I&&-u\\\\0&&1\end{bmatrix}E=\begin{bmatrix}I-uv^T&&0\\\\v^T&&1\end{bmatrix}\tag{5} I0u1 E= IuvTvT01 (5)
    E − 1 = [ I − u v T 0 v T 1 ] − 1 [ I − u 0 1 ] = [ M − 1 − M − 1 u − v T M − 1 1 + v T M − 1 u ] (6) E^{-1}=\begin{bmatrix}I-uv^T&&0\\\\v^T&&1\end{bmatrix}^{-1}\begin{bmatrix}I&&-u\\\\0&&1\end{bmatrix}=\begin{bmatrix}M^{-1}&&-M^{-1}u\\\\-v^TM^{-1}&&1+v^TM^{-1}u\end{bmatrix}\tag{6} E1= IuvTvT01 1 I0u1 = M1vTM1M1u1+vTM1u (6)
  • 由公式4,6 可得,两个 E − 1 E^{-1} E1相等, M = I − u v T M=I-uv^T M=IuvT
    [ I + u D − 1 v T − u D − 1 − D − 1 v T D − 1 ] = [ M − 1 − M − 1 u − v T M − 1 1 + v T M − 1 u ] (7) \begin{bmatrix}I+uD^{-1}v^T&&-uD^{-1}\\\\-D^{-1}v^T&&D^{-1}\end{bmatrix}=\begin{bmatrix}M^{-1}&&-M^{-1}u\\\\-v^TM^{-1}&&1+v^TM^{-1}u\end{bmatrix}\tag{7} I+uD1vTD1vTuD1D1 = M1vTM1M1u1+vTM1u (7)
  • 由第一个行,第一列可得如下
    M − 1 = I + u D − 1 v T = I + u v T 1 − v T u (8) M^{-1}=I+uD^{-1}v^T=I+\frac{uv^T}{1-v^Tu}\tag{8} M1=I+uD1vT=I+1vTuuvT(8)
  • 结论:
    M = I − u v T ⇒ M − 1 = I + u v T 1 − v T u (9) M=I-uv^T\Rightarrow M^{-1}=I+\frac{uv^T}{1-v^Tu}\tag{9} M=IuvTM1=I+1vTuuvT(9)

这篇关于Sherman-Morrison-Woodbury formula 证明的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/972021

相关文章

一种极简的余弦定理证明方法

余弦定理的证明方法有很多种,这里介绍一种极简的证明方法。该方法是本人在工作中推导公式,无意中发现的。证明非常简单,下面简单做下记录。   如上图为任意三角形ABC,以点C为原点,建立直角坐标系(x轴方向任意,y轴与x轴垂直),x轴与CB夹角为 θ 1 \theta_1 θ1​,x轴与CA夹角为 θ 2 \theta_2 θ2​。点B的坐标为 ( a c o s θ 1 , a s i n θ

零知识证明-ZK-SNARKs基础(七)

前言 这章主要讲述ZK-SNARKs 所用到的算术电路、R1CS、QAP等 1:算术电路 算术运算电路 1>半加器:实现半加运算的逻辑电路 2>全加器:能进行被加数,加数和来自低位的进位信号相加,并根据求和结果给出该位的进位信号 说明:2进制加,低位进位 相当于 结果S为 = A+B+C(地位进位) 高位进位 = A+B+C(地位进位) 三个中 有最少2个为1 高位就有进位了 【1】 方程转算

云WAF在安全审计和合规性证明方面起到什么作用?

云WAF在安全审计和合规性证明方面起到什么作用? 云WAF的基本功能 云WAF(Cloud Web Application Firewall)是一种部署在云端的网络安全解决方案,它能够为Web应用程序提供强有力的保护,通过检测和阻止恶意流量、攻击和漏洞,确保Web应用程序的安全性和可用性。云WAF具备访问控制、网络安全审计、漏洞检测、应用安全保护、数据安全监控和审计等功能,这些功能共同构成了一

安全多方计算 同态密文计算 零知识证明 是什么、对比、优缺点

基于计算困难性理论的安全多方计算可以进一步细分为基于混淆电路的方案或者基于秘密分享的方案。 基于混淆电路的方案将所需计算的函数表达成一个巨型的布尔电路,例如,目前表达一次 SHA-256 计算至少需要使用 13 万个布尔门。尽管学术界已经提供了大量优化方案,通用 电路转化的过程依旧很复杂。由于需要使用不经意传输技术来安全地提供电路输入,即便 在有硬件加速的条件下,这类方案的处理吞吐量和计算效率依

再次拿下品牌全球代言人,王鹤棣商业价值再度证明!

9月2日,FENTY BEAUTY品牌正式官宣王鹤棣为全球代言人,这也是该品牌创立至今官宣的中国首位全球代言人。 FENTY BEAUTY是由美国歌手Rihanna创立于2017年的高端美妆品牌,也是LV母公司LVMH集团联手RIHANNA一同孵化的品牌,因其产品具有强包容性,以及能满足消费者多元需求,获得了国际声誉和市场高度认可,品牌全球吸金力排在集团第一梯队,已连年被纳入LVMH集团

使用单个位来存放每个结点的颜色:证明与实现

使用单个位来存放每个结点的颜色:证明与实现 背景知识问题阐述BFS算法的伪代码修改后的BFS算法的伪代码证明过程C语言实现结论 在算法和图论中,染色问题是一个重要的话题,尤其是在处理诸如二分图检测、图的遍历等问题时。本文将探讨在使用广度优先搜索(BFS)算法时,为何仅使用单个位来存放每个结点的颜色即可,并通过详细证明及C语言代码实现来阐述这一点。 背景知识 在图论中,图的遍

【零知识证明】通读Tornado Cash白皮书(并演示)

1 Protocol description 协议描述有以下功能: 1.insert:向智能合约中存入资金,通过固定金额的单笔交易完成,金额由N表示(演示时用1 ETH) 2.remove:从智能合约中提取资金,交易由收款人发起,收款人应该有足够的以太币支付gas费,在这种情况下费用为0(无中继者) 在演示案例中,将实现存款功能和提款功能,无论谁调用提款函数都将是收款人 1.1 Setu

零知识证明-椭圆曲线(四)

前言 零知识证明(Zero—Knowledge Proof),是指一种密码学工具,允许互不信任的通信双方之间证明某个命题的有效性,同时不泄露任何额外信息 上章介绍了基础数字知识,这章主要讲 椭圆曲线 方程 2:椭圆曲线方程 y2+axy+by=x3+cx2+dx+e 式中,a、b、c、d、e均为实数,x和y在实数集上取值。 在加密领域一般采用如下简化后的数学形式: 有限域椭圆曲线 y2= x3+

【零知识证明】构建第一个zk

1 必要步骤 视频学习:5. Circcom 中的基本算术电路_哔哩哔哩_bilibili 文字学习:https://hackmd.io/@YlNLZS2ESI21OSqdTW_mPw/S1jqN-h80/edit 第五课,circom实践,需要安装 1 vscode 2 rust:Windows安装Rust环境(详细教程)-CSDN博客 安装rust出现问题解决方案:Wind

manim动画:利用极限的定义证明极限。

函数的证明 用极限的定义来证明下面的极限。  要用极限的定义证明 ,我们可以使用极限的定义:  设f(x)在包含a的开区间中对所有x≠a有定义,设L为实数。然后  如果,任意一个,存在一个 ,以至于如果对于所有x在f的定义域内,然后  用定义我们得到:,  同时  要用极限的定义证明 ,我们可以使用极限的定义:对任意的,存在 ,使得当 时,有 ,其中 和 。   证