正交匹配追踪算法(Orthogonal Matching Pursuit)实现过程及Python模拟

正交匹配追踪(Orthogonal Matching Pursuit,OMP)是一种用于寻找稀疏信号的贪婪算法,用于求解压缩感知问题中的稀疏近似问题。在压缩感知的背景下,通常我们有一个欠定的线性系统Ax = y,其中A是一个已知的测量矩阵,y是观测到的信号,而x是未知的稀疏信号。OMP 试图找到一个稀疏信号x的解,使得Ax尽可能接近y

定义

OMP算法的目标是解决下面的优化问题:在已知观测向量y和测量矩阵A的情况下,找到一个稀疏的系数向量x,使得Ax尽可能接近于y。这个问题可以用下面的公式表示:

minimize ||x||_0 subject to ||Ax - y||_2 < ε

其中||x||_0x向量的0-范数(即非零元素的数量),而||Ax - y||_2Axy之间的2-范数(即欧几里得距离)。ε是一个容差值,代表了在重构y时所能接受的最大误差。

OMP算法的优点是简单易用、实现快捷,并且相对容易理解。然而由于它是一种贪婪算法,因此有时可能不会找到全局最优解。

应用领域

正交匹配追踪的应用非常广泛,以下是一些主要的应用领域:

  1. 压缩感知:在这个领域中,OMP用于从少量的非自适应线性测量中重构稀疏或压缩的信号。应用包括图像恢复、医学成像(如MRI)、雷达信号处理和无线通信等。

  2. 信号处理:在音频和语音处理、图像处理以及其他信号处理领域中,OMP用于去除噪声、数据压缩、特征提取等任务,特别是在处理信号的稀疏表示时。

  3. 机器学习与数据挖掘:OMP可以作为特征选择方法,帮助从大量特征中选择出对模型影响最为重要的一部分,从而减少模型的复杂性和过拟合的风险。

  4. 计算机视觉:在计算机视觉中,OMP用于目标跟踪、图像分类、图像超分辨率重建和其他图像相关问题。

  5. 生物信息学和遗传学:OMP可以用来识别具有显著生物学作用的基因,通过分析基因表达数据来解析出对某种疾病或条件具有重要影响的生物标志物。

综上所述,正交匹配追踪(OMP)因其在处理稀疏信号重建问题上的简洁性和有效性而被广泛应用于许多科学和工程学科领域。

OMP实现步骤

OMP按以下步骤工作:

  1. 初始化:将解向量x设置为零向量,残差r设置为观测信号y

  2. 迭代直到满足稀疏性要求或残差足够小:

    • 找到与当前残差r最相关的列(原子)从矩阵A中。
    • 更新支持集(包含已选择原子的索引集合)。
    • 求解一个最小二乘问题以更新当前的解x,使Ax最好地拟合y(但只在支持集上的列中)。
    • 计算新的残差r = y - Ax
  3. 输出稀疏解x

Python代码实现

下面是一个使用Python语言实现的OMP算法的例子:

Python

具体代码如下:

# -*- coding: utf-8 -*-
"""
创建于 2024年2月20日 星期二 21:28:40

作者:李立宗

公众号:计算机视觉之光

知识星球:计算机视觉之光

"""

import numpy as np

def omp(A, y, sparsity):
    """
    正交匹配追踪(OMP)算法。
    
    参数:
    A: 测量矩阵
    y: 观测信号
    k: 近似解的期望稀疏度
    
    返回:
    x: 稀疏解向量
    """
    # 初始化
    m, n = A.shape
    x = np.zeros(n)
    residual = y
    idx = []
    
    for _ in range(sparsity):
        # 找到A的列与残差之间最大相关性的索引
        correlations = A.T @ residual
        i = np.argmax(np.abs(correlations))
        idx.append(i)

        # 更新支撑集合并构造限制矩阵
        As = A[:, idx]
        
        # 解决限制为支持集合中索引的A列的最小二乘问题
        x_temp = np.linalg.lstsq(As, y, rcond=None)[0]
        
        # 更新近似解
        x[idx] = x_temp
        
        # 重新计算残差
        residual = y - As @ x_temp
        
        # 检查残差是否接近零
        if np.linalg.norm(residual) < 1e-6:
            break
    
    return x

# 示例用法:
# 信号和测量参数
m = 40    # 观测次数
n = 100   # 稀疏信号的长度
k = 10    # 信号的稀疏级别

# 生成一个随机测量矩阵
A = np.random.randn(m, n)

# 生成一个稀疏信号
x_true = np.zeros(n)
x_true[np.random.choice(n, k, replace=False)] = np.random.randn(k)

# 生成观测信号
y = A @ x_true

# 使用OMP算法
x_pred = omp(A, y, sparsity=k)

# 检查恢复结果
print("原始信号:", x_true)
print("恢复信号:", x_pred)
print("恢复误差:", np.linalg.norm(x_pred - x_true))

在上述代码中,我们首先定义了一个omp函数,该函数接收测量矩阵A,观测到的信号y以及所需的稀疏性水平sparsity。函数返回一个稀疏向量x,它是y的近似解。然后,我们通过一个小例子来描述OMP的应用过程,其中我们先随机生成一个稀疏信号,然后通过OMP算法重构该信号。最后,输出原始信号、重构信号和它们之间的误差。

输出结果

输出结果如下所示:

原始信号: [ 0.          0.          0.          0.          0.          0.
  0.         -1.0476138   0.         -1.16136095  0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.         -1.03891447  0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.5169007   0.
  0.          0.          0.          0.          0.          0.
  0.         -0.58272861  0.          0.          0.         -0.0918172
 -0.26531238  0.          0.          0.          0.          0.
  0.          0.         -0.30563939  0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          1.91814335
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          1.90061899]
恢复信号: [ 0.          0.          0.          0.          0.          0.
  0.         -1.0476138   0.         -1.16136095  0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.         -1.03891447  0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.5169007   0.
  0.          0.          0.          0.          0.          0.
  0.         -0.58272861  0.          0.          0.         -0.0918172
 -0.26531238  0.          0.          0.          0.          0.
  0.          0.         -0.30563939  0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          1.91814335
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          0.          0.          0.
  0.          0.          0.          1.90061899]
恢复误差: 2.182124926419888e-15

在这里插入图片描述

相关博文

理解并实现OpenCV中的图像平滑技术

OpenCV中的边缘检测技术及实现

OpenCV识别人脸案例实战

入门OpenCV:图像阈值处理

我的图书

下面两本书欢迎大家参考学习。

OpenCV轻松入门

李立宗,OpenCV轻松入门,电子工业出版社,2023
本书基于面向 Python 的 OpenCV(OpenCV for Python),介绍了图像处理的方方面面。本书以 OpenCV 官方文档的知识脉络为主线,并对细节进行补充和说明。书中不仅介绍了 OpenCV 函数的使用方法,还介绍了函数实现的算法原理。

在介绍 OpenCV 函数的使用方法时,提供了大量的程序示例,并以循序渐进的方式展开。首先,直观地展示函数在易于观察的小数组上的使用方法、处理过程、运行结果,方便读者更深入地理解函数的原理、使用方法、运行机制、处理结果。在此基础上,进一步介绍如何更好地使用函数处理图像。在介绍具体的算法原理时,本书尽量使用通俗易懂的语言和贴近生活的实例来说明问题,避免使用过多复杂抽象的公式。

本书适合计算机视觉领域的初学者阅读,包括在校学生、教师、专业技术人员、图像处理爱好者。
本书第1版出版后,深受广大读者朋友的喜爱,被很多高校选为教材,目前已经累计重印9次。为了更好地方便大家学习,对本书进行了修订。
在这里插入图片描述

计算机视觉40例

李立宗,计算机视觉40例,电子工业出版社,2022
近年来,我深耕计算机视觉领域的课程研发工作,在该领域尤其是OpenCV-Python方面积累了一点儿经验。因此,我经常会收到该领域相关知识点的咨询,内容涵盖图像处理的基础知识、OpenCV工具的使用、深度学习的具体应用等多个方面。为了更好地把所积累的知识以图文的形式分享给大家,我将该领域内的知识点进行了系统的整理,编写了本书。希望本书的内容能够对大家在计算机视觉方向的学习有所帮助。
本书以OpenCV-Python(the Python API for OpenCV)为工具,以案例为载体,系统介绍了计算机视觉从入门到深度学习的相关知识点。
本书从计算机视觉基础、经典案例、机器学习、深度学习、人脸识别应用等五个方面对计算机视觉的相关知识点做了全面、系统、深入的介绍。书中共介绍了40余个经典的计算机视觉案例,其中既有字符识别、信息加密、指纹识别、车牌识别、次品检测等计算机视觉的经典案例,也包含图像分类、目标检测、语义分割、实例分割、风格迁移、姿势识别等基于深度学习的计算机视觉案例,还包括表情识别、驾驶员疲劳监测、易容术、识别年龄和性别等针对人脸的应用案例。
在介绍具体的算法原理时,本书尽量使用通俗易懂的语言和贴近生活的示例来说明问题,避免使用复杂抽象的公式来介绍。
本书适合计算机视觉领域的初学者阅读,适于在校学生、教师、专业技术人员、图像处理爱好者使用。

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/400200.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

IDEA实现ssh远程连接本地Linux服务器

文章目录 1. 检查Linux SSH服务2. 本地连接测试3. Linux 安装Cpolar4. 创建远程连接公网地址5. 公网远程连接测试6. 固定连接公网地址7. 固定地址连接测试 本文主要介绍如何在IDEA中设置远程连接服务器开发环境&#xff0c;并结合Cpolar内网穿透工具实现无公网远程连接&#xf…

IAR推出新版IAR Embedded Workbench for Arm功能安全版,该版本配备经过认证的静态代码分析功能

瑞典乌普萨拉&#xff0c;2024年2月20日 – 全球领先的嵌入式系统开发软件解决方案供应商IAR宣布&#xff1a;推出其旗舰产品IAR Embedded Workbench for Arm功能安全版的最新版本9.50.3。此次发布进一步加强了IAR支持开发人员创建安全、可靠和符合标准的嵌入式应用程序的承诺&…

回归分析中的异方差性

在简单线性回归或多元线性回归中&#xff0c;我们对误差项做了一些基本假设。 简单线性回归&#xff1a; 多元线性回归&#xff1a; 假设条件&#xff1a; 1.误差均值为零 2.误差具有恒定方差 3.误差不相关 4.误差呈正态分布 第2个假设称为同方差性&#xff0c;因此&…

QML | 信号和信号处理器特性

信号和信号处理器特性 很多时候,应用程序的用户界面组件需要相互通信。例如,一个按钮需要知道用户是否进行了单击:当用户单击后,它可能会更改颜色来指示它状态的改变,或者执行一些逻辑代码实现一定的功能。同Qt一样,QML包含了相似的信号和信号处理器机制。 信号是发出事件…

逻辑回归为什么使用交叉熵而不用均方差?

逻辑回归为什么使用交叉熵而不用均方差&#xff1f;或者说逻辑回归的损失函数为什么不用最小二乘&#xff1f; 下面主要从两个角度进行阐述&#xff1a; 从逻辑回归的角度出发&#xff0c;逻辑回归的预测值是一个概率&#xff0c;而交叉熵又表示真实概率分布与预测概率分布的…

(C++) 详解内存地址空间

详解内存空间 0. 概述 一个C/C 程序&#xff0c;编译之后&#xff0c;形成的程序&#xff0c;在执行期间&#xff0c;内存中不仅存在一块区域用于存放代码&#xff0c;还有一些其他的区域用于使用&#xff0c;本节会详解C/C内部所使用的内存地址空间&#xff0c;关于各内存的…

每日OJ题_二叉树dfs③_力扣814. 二叉树剪枝

目录 力扣814. 二叉树剪枝 解析代码 力扣814. 二叉树剪枝 814. 二叉树剪枝 难度 中等 给你二叉树的根结点 root &#xff0c;此外树的每个结点的值要么是 0 &#xff0c;要么是 1 。 返回移除了所有不包含 1 的子树的原二叉树。 节点 node 的子树为 node 本身加上所有 n…

深入探索Selenium自动化测试:基础、代码实战与最佳实践【第90篇—Selenium自动化测试】

文章目录 深入探索Selenium自动化测试&#xff1a;基础、代码实战与最佳实践什么是Selenium&#xff1f;安装Selenium基础用法启动浏览器查找元素操作元素 代码实战&#xff1a;模拟登录进阶用法等待元素出现处理弹窗执行JavaScript 高级应用&#xff1a;Selenium Grid启动Sele…

压缩感知常用的测量矩阵

测量矩阵的基本概念 在压缩感知&#xff08;Compressed Sensing&#xff0c;CS&#xff09;理论中&#xff0c;测量矩阵&#xff08;也称为采样矩阵&#xff09;是实现信号压缩采样的关键工具。它是一个通常为非方阵的矩阵&#xff0c;用于将信号从高维空间映射到低维空间&…

基于vue框架的环保知识普及平台设计与实现

项目&#xff1a;基于vue框架的环保知识普及平台设计与实现 目 录 摘要 I Abstract II 第1章 引言 1 1.1 研究的背景 1 1.2 目的和意义 1 1.3 设计思路 1 1.4 研究的主要内容 2 第2章 相关原理和技术 3 2.1 B/S 模式体系结构 3 2.2 Springboot技术 4 2.3 访问数据库…

“中国国安部紧急警告”!境外公司利用加密货币诱使人员非法采集空间数据!当心不慎成“帮凶”!

随着加密货币的普及&#xff0c;每天都有新的区块链项目出现&#xff0c;目前市场上已经有成千上万种不同的加密货币 一些项目可能因其名人光环、运作机制、出色的代币经济学、或是提供优良的服务而受到市场亲睐&#xff0c;但也有很多项目缺乏大众的关注&#xff0c;或是尚未有…

机器学习——强化学习作业

作业内容 成功降落在两个黄色旗子中间为成功&#xff0c;其他为失败 Policy Gradient方法 Actor-Critic方法 范例结果 baseline Policy Gradient实现

初阶数据结构之---顺序表和链表(C语言)

引言-线性表 线性表&#xff1a; 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构&#xff0c;也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上…

OSQP文档学习

OSQP官方文档 1 QSQP简介 OSQP求解形式为的凸二次规划&#xff1a; x ∈ R n x∈R^n x∈Rn&#xff1a;优化变量 P ∈ S n P∈S^n_ P∈Sn​&#xff1a;半正定矩阵 特征 &#xff08;1&#xff09;高效&#xff1a;使用了一种自定义的基于ADMM的一阶方法&#xff0c;只需…

【Flink精讲】Flink内核源码分析:命令执行入口

官方推荐per-job模式&#xff0c;一个job一个集群&#xff0c;提交时yarn才分配集群资源&#xff1b; 主要的进程&#xff1a;JobManager、TaskManager、Client 提交命令&#xff1a;bin/flink run -t yarn-per-job /opt/module/flink-1.12.0/examples/streaming/SocketWind…

什么是CODESYS开发系统

CODESYS是一种用于工业自动化领域的开发系统软件&#xff0c;提供了一个完整集成的开发环境。该软件由德国CODESYS GmbH&#xff08;原 3S-Smart Software Solutions GmbH&#xff09;公司开发&#xff0c;其最新版本为CODESYS V3。 CODESYS开发系统具有多种特性和优点。首先&a…

Linux内核解读

来自鹅厂架构师 作者&#xff1a;aurelianliu 工作过程中遇到的调度、内存、文件、网络等可以参考。 1.os运行态 X86架构&#xff0c;用户态运行在ring3&#xff0c;内核态运行在ring0&#xff0c;两个特权等级。 &#xff08;1&#xff09;内核、一些特权指令&#xff0c;例…

JS实现根据数组对象的某一属性排序

JS实现根据数组对象的某一属性排序 一、冒泡排序&#xff08;先了解冒泡排序机制&#xff09;二、根据数组对象的某一属性排序&#xff08;引用sort方法排序&#xff09; 一、冒泡排序&#xff08;先了解冒泡排序机制&#xff09; 以从小到大排序为例&#xff0c;冒泡排序的原…

typescript映射类型

ts映射类型简介 TypeScript中的映射类型&#xff08;Mapped Type&#xff09;是一种高级类型&#xff0c;它允许我们基于现有类型创建新的类型&#xff0c;同时对新类型的每个属性应用一个转换函数。通过使用映射类型&#xff0c;我们可以方便地对对象的属性进行批量操作&…

人工智能深度学习

目录 人工智能 深度学习 机器学习 神经网络 机器学习的范围 模式识别 数据挖掘 统计学习 计算机视觉 语音识别 自然语言处理 机器学习的方法 回归算法 神经网络 SVM&#xff08;支持向量机&#xff09; 聚类算法 降维算法 推荐算法 其他 机器学习的分类 机器…