CS754 - Advanced Image Processing Sheel Shah - 19D070052 Kushal Kejriwal - 190110040

2025-05-06 0 0 585.67KB 14 页 10玖币

侵权投诉

CS754 - Advanced Image Processing

Sheel Shah - 19D070052

Kushal Kejriwal - 190110040

Compressive Image Classiﬁcation using Deterministic

Sensing Matrices

Part 1 - Deterministic Sensing Matrices

We have studied compressive sensing, where the goal is to capture majority of the information in

the signal using very few measurements and obtain accuracte reconstructions. One of the most

important aspect of compressive sensing was the design of sensing matrices Φand we understood

that if the sensing matrices obey the Restricted Isometry Property, and obtained worst case

performances on the reconstructed signals.

Let the signal be ssparse, let the dimension of the signal be Nand let the number of measurements

be m. In particular, we looked at random sensing matrices that satisfy the RIP property with

overwhelming probability with the overwhelming property given that:

m≥ O(slog(N/s))

In our course, we have looked at random sensing matrices, and how they satisfy the RIP property

that helps us in obtaining the worst case error bounds. This is analogous to Shannon’s coding

theory, that also provides a worst case error for a transmission channel and thus the random

sensing matrices are associated with certain drawbacks which are described below:

1. Time Complexity during Reconstruction: We have looked at a few algorithms to

reconstruct signals from the measurements and some of them include the Basis Pursuit

algorithm and the Orthogonal Matching Pursuit algorithm. The time complexity of these

signals are given in Table 1. In contrast, we can construct eﬃcient reconstruction algorithms

with lower time complexities.

2. Storing the Random Sensing Matrix: This requires signiﬁcant space, especially if the

dimension of signal is large. In contrast, entries of the deterministic sensing matrix can be

computed on the ﬂy, and thus no need of storage is required.

arXiv:2210.10777v1 [eess.IV] 15 Oct 2022

Sheel Shah, Kushal Kejriwal CS754 Course Project

3. Verifying the RIP property: There is no eﬃcient algorithm for verifying whether the

given sensing matrix obeys the RIP property. In the course we looked at an (ineﬃcient)

algorithm based on subset ennumeration with O(Ns)time complexity.

Algorithm Time Complexity

Basis Pursuit O(N3)

Orthogonal Matching Pursuit O(s2logα(N))

Table 1: Time Complexities of Common Reconstruction Algorithms

An important thing to consider here is analogous to coding theory, instead of the worst-case error

we will analyse the typical (expected error) while studying deterministic sensing matrices.

StRIP and UStRIP

For dealing with deterministic sensing matrices, we will impose a weaker version of the Restricted

Isometry Property, namely the Statistical Restricted Isometry Property.

Deﬁnition 0.1 (k, e, δ - StRIP matrix).An m×Nsensing matrix Φis said to be a k, , δ - StRIP

matrix, if for ksparse vectors α∈RN, the following equation:

(1 −)kαk2≤ kφαk2≤(1 + )kαk2

holds with probability exceeding 1−δ

Note that this deﬁnition does not imply unique reconstruction, even with an exceedingly high

probability. This is because the number of s-sparse vectors α∈RNsuch that there is a diﬀerent

s-sparse β∈RNfor which Φα= Φβbeing small is a much more strict condition than number of

s-sparse vectors β∈RNand Φα= Φβbe small. Note that the StRIP deﬁnition guaranteed the

latter condition but not the former, and this is why we deﬁne the Unique Statistical Restricted

Isometry Property as follows:

Deﬁnition 0.2 (k, e, δ - UStRIP matrix).An m×Nsensing matrix Φis said to be a k, , δ -

UStRIP matrix, if Φis a (k, e, δ - StRIP matrix) and

{β∈RN,Φα= Φβ}={α}

holds with probability exceeding 1−δ

StRIP-able Matrices

We will now look at a few simple design rules, which are suﬃcient to guarantee that Φis a UStRIP

matrix, and these properties are satisﬁed by a large class of matrices.

Deﬁnition 0.3. An m×N- matrix Φis said to be η- StRIP-able, where ηsatisﬁes 0< η < 1,

if the following conditions are satisﬁed:

•St1: The rows of Φare orthogonal, and all the row sums are 0

Sheel Shah, Kushal Kejriwal CS754 Course Project

•St2: The columns of Φform a group under pointwise multiplication as follows:

For all j, j0∈ {1,2, ...., N},there exists a j00 such that φjφj0=φj00

•St3: For all j∈ {2, ...., N}|X

φj(x)|2≤N2−η

Main Result

Theorem 1. Suppose the m×Nmatrix Φis ηStRIP-able, and suppose k < 1 + (m−1)

and η > 1/2. Then there exists a constant c such that, if m≥cklog(N)

21/η

, then Φis

(k, , δ)−UStRIP with δ= 2 exp −[−(k−1)/(N−1)2]mη

8k

The authors also suggest the Quadratic Reconstruction Algorithm, which only requires vector-

vector multiplication in the measurement domain, and thus has a sub-linear time complexity with

respect to N(the dimension of the signal). The StRIP property provides performance guarantees,

because eﬀectively the algorithm returns the location of one of the ksigniﬁcant entries, and the

property guarantees that the estimate is within of the true value.

Delsarte - Goethals Frames

Having introduced deterministic matrices for the purpose of compressive classiﬁcation, we will now

look at a particular type of deterministic matrices - the Delsarte-Goethals Frames. We will then

show that these matrices are StRIP-able by proving that they obey the properties mentioned above.

We will also show that these matrices when used for the purpose of compressive classiﬁcation

using Support Vector Machines give performance bounds with respect to classiﬁcation in the data

domain.

Deﬁnition 0.4. A group is a set of elements Ωwith some operation ∗such that ∗is associative,

invokes an identity element in Ωand ∀x, y ∈Ω, x ∗y∈Ω

Deﬁnition 0.5. A Delsarte-Goethals set DG(m, r) is a set of 2(r+1)mm×mbinary symmetric

matrices with the property that ∀A, B ∈DG(m, r)and A 6=B, rank(A−B)≥m−2r

Deﬁnition 0.6. A Delsarte-Goethals frame G(m, r) is a 2m×2(r+2)mmatrix with each element

deﬁned as:

a(P,b),t =iwt(dP)+2wt(b)·itP tT+2btT/√m

where:

tis a binary m-tuple used to index rows of the matrix

Pis a m×mmatrix in DG(m, r),

bis a binary m-tuple

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

CS754-AdvancedImageProcessingSheelShah-19D070052KushalKejriwal-190110040CompressiveImageClassicationusingDeterministicSensingMatricesPart1-DeterministicSensingMatricesWehavestudiedcompressivesensing,wherethegoalistocapturemajorityoftheinformationinthesignalusingveryfewmeasurementsandobtainaccuracte...

展开>> 收起<<

CS754 - Advanced Image Processing Sheel Shah - 19D070052 Kushal Kejriwal - 190110040.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

CS754 - Advanced Image Processing Sheel Shah - 19D070052 Kushal Kejriwal - 190110040

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: