text:
International Association for Cryptologic Research

# IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2013-10-28
21:17 [Pub][ePrint]

Secure communication is a fundamental cryptographic primitive. Typically, security is achieved by relying on an existing credential infrastructure, such as a PKI or passwords, for identifying the end points to each other. But what can be obtained when no such credential infrastructure is available?

Clearly, when there is no pre-existing credential infrastructure, an adversary can mount successful man in the middle\'\' attacks by modifying the communication between the legitimate endpoints. Still, we show that not all is lost, as long as the adversary\'s control over the communication is not complete: We present relatively efficient key exchange and secure session protocols that provide the full guarantee of secure communication as long as the adversary fails to intercept even a single message between the legitimate endpoints.

To obtain this guarantee we strengthen the notion of key exchange to require that the keys exchanged in any two sessions are independent of each other as long as each session has at least one honest endpoint, even if both sessions has an adversarial endpoint. We call this notion credential-free key exchange. We then strengthen the existing notion of secure session protocols to provide the above guarantee given a CFKE (existing definitions and constructions are insufficient for this purpose). We provide two alternative definitions and constructions of CFKE, a game-based one with a construction in the RO model, and a UC one with a construction in the CRS model.

21:17 [Pub][ePrint]

Oblivious RAM (ORAM) has recently attracted a lot of interest since

it can be used to protect the privacy of data user\'s data access pattern from (honest but curious) outsourced storage. This is

best known multi-server ORAM scheme, our write-only ORAM schemes have lower (typically one order lower) communication cost, or achieve the same communication cost with the same client-side storage usage in single-server setting. (ii) the data owner\'s personal use: Our write-only ORAM schemes combined with PIR can be used as building blocks for some existing full functional ORAM schemes. This leads to the reduction of the communication costs for two full-functional ORAM schemes by the factors of $O(\\log N)$ and $O(\\sqrt{\\log N}\\times \\log\\log N)$, where $N$ is the maximum data item count. One of these resulting schemes has a communication cost of $O(l)$, where $l$ is data item length. This is typically one order lower than the previous best known ORAM scheme\'s cost, which is $O(\\log N \\times l)$. The other resulting scheme also achieves $O(\\log N \\times l)$ communication cost, but its client-side storage usage is several orders lower than the best known single-server ORAM\'s.

21:17 [Pub][ePrint]

This paper introduces a dedicated authenticated encryption algorithm AEGIS; AEGIS allows for the protection of associated data which makes it very suitable for protecting network packets. AEGIS-128L uses eight AES round functions to process a 32-byte message block (one step). AEGIS-128 uses five AES round functions to process a 16-byte message block (one step); AES-256 uses six AES round functions. The security analysis shows that these algorithms offer a high level of security. On the Intel Sandy Bridge Core i5 processor, the speed of AEGIS-128L, AEGIS-128 and AEGIS-256 is around 0.48, 0.66 and 0.7 clock cycles/byte (cpb) for 4096-byte messages, respectively. This is substantially faster than the AES CCM, GCM and OCB modes.

21:17 [Pub][ePrint]

It has become much easier to crack a password

hash with the advancements in the graphicalprocessing

unit (GPU) technology. An adversary can

recover a user\'s password using brute-force attack on

password hash. Once the password has been recovered

no server can detect any illegitimate user authentication

(if there is no extra mechanism used).

In this context, recently, Juels and Rivest published a

paper for improving the security of hashed passwords.

Roughly speaking, they propose an approach for user

authentication, in which some false passwords, i.e., \"honeywords\"

are added into a password file, in order to

detect impersonation. Their solution includes an auxiliary

secure server called \"honeychecker\" which can distinguish

a user\'s real password among her honeywords and immediately

sets off an alarm whenever a honeyword is used.

In this paper, we analyze the security of the proposal and

provide some possible improvements which are easy to

implement

21:17 [Pub][ePrint]

Threshold Implementations provide provable security against first-order power analysis attacks for hardware and software implementations. Like masking, the approach relies on secret sharing but it differs in the implementation of logic functions. At \\textsc{Eurocrypt} 2011 Moradi et al. published the to date most compact Threshold Implementation of AES-128 encryption. Their work shows that the number of required random bits may be an additional evaluation criterion, next to area and speed. We present a new Threshold Implementation of AES-128 encryption that is 18\\% smaller, 7.5\\% faster and that requires 8\\% less random bits than the implementation from \\textsc{Eurocrypt} 2011. In addition, we provide results of a practical security evaluation based on real power traces in adversary-friendly conditions. They confirm the first-order attack resistance of our implementation and show good resistance against higher-order attacks.

21:17 [Pub][ePrint]

In 2012, Alagheband and Aref presented a dynamic and secure key manage

ment model for hierarchical heterogeneous sensor networks. They proposed a signcryption algorithm which is the main building block in their key management model. They proved the algorithm is as strong as the elliptical curve discrete logarithm problem. In this work,

we study the security of their signcryption algorithm. It is regretful that we found their algorithm is insecure. The adversary can impersonate the base station by sending forged messages to the cluster leaders after capturing the signcrypted messages. Hence, the key management model proposed by them is insecure. Then, we propose an improved signcryption algorithm to fix this weakness.

21:17 [Pub][ePrint]

We show that it is possible to upgrade an obfuscator for a weak complexity class $\\weak$ into an obfuscator for arbitrary polynomial size circuits, assuming that the class $\\weak$ can compute pseudorandom functions. Specifically, under standard intractability assumptions (e.g., hardness of factoring, Decisional Diffie--Hellman, or Learning with Errors), the existence of obfuscators for $\\NC^1$ or even $\\TC^0$ implies the existence of general-purpose obfuscators for $\\classP$. Previously, such a bootstrapping procedure was known to exist under the assumption that there exists a fully-homomorphic encryption whose decryption algorithm can be computed in $\\weak$. Our reduction works with respect to virtual black-box obfuscators and relativizes to ideal models.

21:17 [Pub][ePrint]

We describe a new algorithm for masking look-up tables of block-ciphers at any order, as a countermeasure against side-channel attacks. Our technique is a generalization of the classical randomized table countermeasure against first-order attacks. We prove the security of our new algorithm against t-th order attacks in the usual Ishai-Sahai-Wagner model from Crypto 2003; we also improve the bound on the number of shares from n>=4t+1 to n>= 2t+1 for an adversary who can adaptively move its probes between successive executions.

Our algorithm has the same time complexity O(n^2) as the Rivain-Prouff algorithm for AES, and its extension by Carlet et al. to any look-up table. In practice for AES our algorithm is less efficient than Rivain-Prouff, which can take advantage of the special algebraic structure

of the AES Sbox; however for DES our algorithm performs slightly better.

21:17 [Pub][ePrint]

We show that if there exist indistinguishability obfuscators for a certain class C of circuits then there do not exist independent-auxiliary-input virtual-black-box (VBB) obfuscators for any family of circuits that compute a pseudo-entropic function. A function f_k is pseudo-entropic if it is hard, given oracle access to f_k but without asking explicitly on a value x, to distinguish f_k(x) from a random variable with some real entropy.

This strengthens the bound of Goldwasser and Kalai [FOCS 05, ePrint 13] that rules out dependent-auxiliary-input VBB obfuscation for the same set of circuit families, assuming inditinguishability obfuscators for another class, C\', of circuits. That is, while they only rule out the case where the adversary and the simulator obtain auxiliary information that depends on the actual (secret) obfuscated function, we rule out even the case where the auxiliary input depends only

on the (public) family of programs.

21:17 [Pub][ePrint]

Non-malleable codes, defined by Dziembowski, Pietrzak and Wichs (ICS \'10), provide roughly the following guarantee: if a codeword $c$ encoding some message $x$ is tampered to $c\' = f(c)$ such that $c\' \\neq c$, then the tampered message $x\'$ contained in $c\'$ reveals no information about $x$. Non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks.

One cannot have an efficient non-malleable code that protects against all efficient tampering functions $f$. However, in this work we show the next best thing\'\': for any polynomial bound $s$ given a-priori, there is an efficient non-malleable code that protects against all tampering functions $f$ computable by a circuit of size $s$. More generally, for any family of tampering functions $\\F$ of size $|\\F| \\leq 2^{s}$, there is an efficient non-malleable code that protects against all $f \\in \\F$. The rate of our codes, defined as the ratio of message to codeword size, approaches $1$. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the common reference string\'\' (CRS) model.

We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x\' = f(x)$, the derived key $y\' = h(x\')$ does not reveal any information about $y$. Our results for non-malleable key derivation are analogous to those for non-malleable codes.

As a useful tool in our analysis, we rely on the notion of leakage-resilient storage\'\' of Davi, Dziembowski and Venturi (SCN \'10) and, as a result of independent interest, we also significantly improve on the parameters of such schemes.

2013-10-24
18:17 [Pub][ePrint]

Bideniable encryption allows both sender and receiver in a public-key setting to simultaneously claim that a different message of their choice was transmitted, and support this claim by a good-looking encryption and key-generation randomness, respectively. A weaker version with two variants of algorithms is called flexible or multi-distributional deniability, a stronger one-algorithm version is called full deniability. Bendlin et al. (ASIACRYPT 2011) showed that certain kinds of fully-deniable schemes are constructible using corresponding flexible schemes. In this paper, we show that their construction in the bideniable case has a flaw, and we provide a fixed scheme. Our construction relies on a deterministic subset matching algorithm that assigns to each nonempty subset of a finite set its proper subset reduced by exactly one element. Although this algorithm is crucial in our construction, it may also be of independent interest.


text:
# nose-exclude /

Filename Size Date modified Message
test_dirs
470 B
91 B
852 B
23.9 KB
19 B
2.2 KB
3.2 KB
1019 B
3.5 KB
85 B

## Overview

nose-exclude is a Nose plugin that allows you to easily specify directories to be excluded from testing.

## Exclude Directories

The --exclude-dir= option is made available after installation of the plugin. The option may be used multiple times to exclude multiple directories from testing. The directory paths provided may be absolute or relative.

Example:

$nosetests --exclude-dir=test_dirs/build \ --exclude-dir=test_dirs/test_not_me test_dirs .... ---------------------------------------------------------------------- Ran 4 tests in 0.006s OK  This example will exclude the directories test_dirs/build and test_dirs/test_not_me from nosetests' test searching. ### Using File-Based Exclusion List The --exclude-dir-file= option can be used to pass in a predefined list of directories contained within a file. nose-exclude expects each directory to be excluded to be on its own line. Example: $ nosetests --exclude-dir-file=test_dirs/exclude_dirs.txt \
test_dirs
....
----------------------------------------------------------------------
Ran 4 tests in 0.006s

OK

where exclude_dirs.txt might look like:

test_dirs/build
# Start a line with a '#' to include
test_dirs/test_not_me

### Using Environment Variables

--exclude-dir= can be set by the environment variables NOSE_EXCLUDE_DIRS. Multiple exclude paths may be entered by separating them using a ;. The environment variable NOSE_EXCLUDE_DIRS_FILE when set to the path of a file-based exclusion list functions as though it were passed in with --exclude-dir-file=.

## Nose Configuration Files

nose-exclude options can also be passed to nosetests using a .noserc or nose.cfg file. If you more than one directory are to be excluded separate their values with newlines using the same configuration key:

[nosetests]
exclude-dir=test_dirs/exclude_dirs
test_dirs/more_excludes

## Bugs

Please report all bugs (and patches) to http://bitbucket.org/kgrandis/nose-exclude/

format: plain


text:
# What is wrong in the code for this upwind method?

I want to implement the upwind method in following advection equation problem :
$$u_{t}+2 u_{x} =0 ,$$ for $$0\leq t \leq 1,$$ $$0\leq x \leq 1$$ $$u(0,x) = u_{0}(x) = \begin{cases} 10^4 (0.1-x)^2 (0.2-x)^2 & 0 < x < 0.2 \\ 0 & otherwise \end{cases}$$ with wind coefficient $$\alpha = 2$$ , $$Nt = 100$$ ,$$Nx = 250$$ resulting to Courant number $$v = 0.4$$

But it doesn't seem right.What i do wrong? I would appreciate any help.

import numpy as np
import matplotlib.pyplot as plt

class UpwindMethod:

def __init__(self, Nx,Nt, tmax):
self.Nx = Nx                # number of space nodes
self.Nt = Nt                # number of time  nodes
self.tmax = tmax
self.xmin = 0
self.xmax = 1
self.dt =   tmax/self.Nt    # timestep
self.a =    2               # velocity
self.v =    (self.a * self.dt ) / ((self.xmax - self.xmin)/self.Nx)
self.initializeDomain()
self.initializeU()
self.initializeParams()

def initializeDomain(self):
self.dx = (self.xmax - self.xmin)/self.Nx
self.x = np.arange(self.xmin-self.dx, self.xmax+(2*self.dx), self.dx)

def initializeU(self):
u0 = np.where( (0.1<self.x) & (self.x<0.2) , ((10**4)*((0.1-self.x))**2 *((0.2-self.x)**2))   ,0)
self.u = u0.copy()
self.unp1 = u0.copy()

def initializeParams(self):
self.nsteps = round(self.tmax/self.dt)

def solve_and_plot(self):
tc = 0.

for n in range(self.nsteps):
plt.clf()
for i in range(self.Nx+2):
self.unp1[i] = self.u[i] - ((self.a*self.dt)/(self.dx))*(self.u[i]-self.u[i-1])

self.u = self.unp1.copy()

# Periodic boundary conditions
self.u[0] = self.u[self.Nx+1]
self.u[self.Nx+2] = self.u[1]

uexact = np.where( (0.1<self.x) & (self.x<0.2) , ((10**4)*((0.1-self.x-self.a* tc)**2) *((0.2-self.x-self.a* tc)**2))   ,0)

plt.plot(self.x, uexact,  label=" Exact solution ")
plt.plot(self.x, self.u,  label=" Upwind Approximation ")

plt.xlabel("x")
plt.ylabel("u")
plt.legend(loc=1, fontsize=13)
tc += self.dt

def main():
sim = UpwindMethod(100,250, 0.02)
sim.solve_and_plot()
plt.show()
if __name__ == "__main__":
main()

$$$$

• It might help to show a plot of the solution and discuss why you think it is incorrect. – Paul Nov 13 '20 at 14:49

I've identified a few "problems":

1. Your analytical solution isn't quite correct. The correct analytical solution to the "infinite domain" advection equation is supposed to be $$u(t,x) = u_0(x-at)$$. Because you have periodic boundaries, you need to properly account for this by making sure $$x-at$$ is properly wrapped.

I replaced your initializeU function with one which just computes u(t,x):

def exact_u(self, t):
# this properly wraps your analytical solution for periodic BC's
xp = (self.x - self.a*t - self.xmin)%(self.xmax-self.xmin) + self.xmin
u0 = np.where( (0.1<xp) & (xp<0.2) , ((10**4)*((0.1-xp))**2 *((0.2-xp)**2)), 0)
return u0

You will also need to update the __init__ or initializeU function to correctly use this function by just calling it for the exact solution at $$t=0$$.

In addition to this, where you're using this in the solve_and_plot function is comparing the simulation results with the exact solution 1 timestep prior, so you should change it to:

tc += self.dt
uexact = self.exact_u(tc)

1. I don't think you're handling the periodic BC's correctly in your simulation. There's not really any need to create extra nodes at the exterior, since you can take advantage of Python's negative indexing to index to the end of the array automatically with your 2 node upwind stencil. You also have to take into account the fact that the very first node and last node are effectively "coincident" and supposed to be identical.

You can handle this by stopping one $$\Delta x$$ short at the end, since it's just a duplicate node, however this does look a bit weird since you're not plotting to the end of your periodic domain. Here's a solution which circumvents this by doing some slicing to handle the simulation correctly while still having an extra storage space for the end node:

    def initializeDomain(self):
self.dx = (self.xmax - self.xmin)/self.Nx
self.x = np.linspace(self.xmin, self.xmax, self.Nx + 1)

def solve_and_plot(self):
tc = 0.

for n in range(self.nsteps):
plt.clf()
# periodic BC's automatically handled by Python's negative indexing
# use slices to ensure we skip the duplicate end node only there for plotting purposes
unp1 = self.unp1[:-1]
u = self.u[:-1]
for i in range(u.shape[0]):
unp1[i] = u[i] - ((self.a*self.dt)/(self.dx))*(u[i]-u[i-1])

# update the duplicate end node's value
u[-1] = u[0]

self.u = self.unp1.copy()

#... rest of this function

1. As you've probably noticed when you have a $$v < 1$$, the simulation is stable but diffusive (becoming less diffusive as $$v \rightarrow 0$$. This is simply a fundamental numerical error associated with how you chose to discretize the method. You can "magically" avoid this for this problem by using a timestep which gives you exactly a $$v = 1$$ (this doesn't always work). In this case, this requires $$\Delta t = \frac{\Delta x}{a}$$, or Nt = 4`. As a side-note, I think you're calculating your Courant number incorrectly; it's supposed to be: $$v = \frac{a \Delta t}{\Delta x}$$

$$v = 1$$ (Nt = 4, $$t_{end} = 0.02$$):

$$v = 0.016$$ (Nt = 250, $$t_{end} = 0.02$$):


text:
# Chemical equilibrium problem

$LaTeX: \min \left\{ c^Tx + \sum_j \left(x_j \ln(x_j) \right) : x > 0, \; \sum\limits_j x_j = M, \; Ax=b \right\},$
where the objective is the Gibbs free energy function with $LaTeX: x_j$ being the number of moles of species $LaTeX: j$, $LaTeX: b_i$ being the atomic weight of atom of type $LaTeX: i$, and $LaTeX: A_{i,j}$ being the number of atoms of type $LaTeX: i$ in one mole of species $LaTeX: j$. The equation, $LaTeX: Ax=b$, is mass balance. (Its significance is that it was an early application to show how an LP approach can apply to a nonlinear mathematical program.)


text:
# Tag Info

## Hot answers tagged brute-force-attack

67

256-bit key cracking through exhaustive search is totally out of reach of Mankind. And it takes quite a lot of wishful thinking to even envision a 128-bit key cracking: trying one key must be reduced to the flip of a single logic gate (compared to the hundreds of thousands which are actually required); that gate must be more energy-efficient than the most ...

52

The average cost for electricity in the US is $\$0.12$per kWh. For a single server I'll use 3741 kWh annually as an estimate. That would be about$\$450$ per year for one machine. Let's say you can do $10^{14}$ decryptions per second. That is $3.15*10^{21}$ decrypts per year for one machine. You need to do (on average) $2^{255}$ decryptions in a year, so ...

47

There is some Thermodynamic Limitations. A good explanation about Thermodynamic Limitations is by Bruce Schneier in Applied Cryptography: One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of ...

25

Assume that 1 evaluation of {DES, AES} takes 10 operations, and we can perform $10^{15}$ operations per second. Trivially, that means we can evaluate $10^{14}$, or about $2^{46.5}$ {DES, AES} encryptions per second. This is a simplistic view: we are ignoring here the cost of testing whether we found the correct key, and the key schedule cost. So on our ...

17

According to this source, bitcoin mining nowadays (Nov. 2015) tops $500\cdot10^{15}$ hashes per second, where one hash is two nested SHA-256; that is over $2^{84.7}$ SHA-256 per year. I'm guessing the NSA could do much better with a fraction of its budget. Here is this data redrawn in SHA-256 per year with a $\log_2$ vertical scale, to facilitate comparison ...

16

Yes, a computationally unbounded attacker can break any public key system. One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK. Now, what a computationally unbounded adversary can do is ...

14

n is the exponent. So when n is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$). It is required to only search half of the key space on average (if average is the correct term ...

12

XXTEA (also known as Corrected Block TEA) is a block cipher with $128$-bit key and block width parameterizable to $n\cdot32$ bits for $n\ge2$. It is an Unbalanced Feistel Cipher making $q=6+\lfloor52/n\rfloor$ passes over the block, with $q\cdot n$ rounds each modifying $32$ bits of the block. In Cryptanalysis of XXTEA, it is presented a chosen-plaintext ...

11

From the perspective of someone who is a non-cryptographer but runs penetration tests against, well, anything really, there is a very simplistic answer that is generally correct in the real world: Assuming the implementation of the encryption algorithm is not flawed (I know, not always a good assumption, but the common open source tools get a lot of peer ...

11

If (you suspect that) the (plaintext of the) encrypted data is ASCII text, you can check if the high bit of each decrypted byte is zero. As long as you have more than 24 bytes of data to check, the odds of that happening by chance are pretty low (given that you have a 24-bit keyspace). UTF-8 text is also pretty easy to detect, since all bytes that do have ...

10

It's not possible. The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of $512$ bit primes (approximately the length you need for $1024$ bit modulus) is approximately: $$\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$$ The number of RSA moduli (i.e. pair of two distinct primes) is ...

10

Not all ciphers can be broken, even by infinitely powerful adversaries. When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it can't be broken with cryptanalysis. However, part of being provably secure is that you need at least as much key material as you have plaintext to encrypt. Such a key needs to be shared between ...

9

Non-technical brute force method: The most cost-effective "brute-force" method I can think of is to hire a gang of mobsters to force the guy who knows the password into giving it up. For a guy with no security, a good mobster would probably cost about \$5,000, and you'd need at least 3 of them. If you are going for a high-profile guy, a good mobster would ... 9 Re-using their design might be no good idea - there are cheaper designs for sure. This new DES cracker would just need to try every possible key - like the one of the EFF already did. DES was a big standard for encryption, so some people did build such machines, right? Of course did they: COPACOBANA is able to break DES in under 9 days and costs under ... 8 The last major effort I know of for cracking keys was the Distributed.net effort. You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP ... 8 Assuming the n-bit CRC of an unknown bit string b is known, one can constructively rebuild any consecutive n bits of b from the rest of the bit string (and the definition of the CRC). Indeed, in the case described, that speeds up password search considerably. One can compute the last 32 bits of the password (likely, 4 characters) from the beginning of the ... 8 This is called ciphertext-only cryptanalysis*, and it's pretty difficult unless the cipher is quite weak. Therefore, the first priority for a cryptanalyst in such a situation is usually to try to find more information about the algorithm. Fortunately (for the cryptanalyst), as Kerckhoff's principle suggests, there are often ways to find out how the ... 8 Why can't you simply ask the person who made that file to tell you the password? No one knows how to decode an AES-encrypted file, such as password-protected WinRar files, without knowing the password. As far as we know, the only way to decode AES-encrypted files is to somehow obtain the right password, and then use that password to decrypt the file. In ... 8 I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar). If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude. For example, the ... 8 Any protocol with long-term security becomes harder to break after the protocol execution has finished. In the Bounded-Storage Model, protocols become harder of break as [information about the randomizer that's not stored by the adversary] is lost.$\:$(This point is similar to minar's observation.) 8 The Bitcoin mining algorithm can not be simplified by exploiting any weakness in the SHA-2 hashing algorithm with the current state of the art. The problem is manyfold. From the SHA-256 point of view, there is no (partial) preimage search algorithm that applies to the full hash function. Even worse, the attacks that penetrate a fewer number of rounds have ... 8 There are multiple metrics for work or effort needed: Amount of operations it takes (one operations is, for instance, one invocation of hash function or number of modular multiplication operations) Amount of money it takes Amount of memory it takes Amount of time it takes Strength in bits Amount of operations Usually, if amount of operations is large ... 8 A key size of 80 bits is the historical limit of infeasibility; that's what was used in the 1990s as a rule of thumb. That's the reason why Skipjack used an 80-bit key, and SHA-1 offers a 160-bit output. Various people have also estimated that a 1024-bit RSA, DH or DSA key offers an "80-bit equivalent" protection (see this site). One of the most optimistic ... 8 This answer addresses Cases 1 and 2 from the question to provide a baseline, leaving Case 3 (which is the one I'm most interested in), unresolved. Case 1, Zero Increment In this case we'll consider a simple Lehmer-style LCG (a.k.a. an MCG), with a seed$s_1$, multiplier$a$and$b$bits of state and$r$bits returned. The modulus$M = 2^b$, and the ... 7 The classic way to do this is to have all parties commit to individual random values by publishing a secure hash of a suitably random-nonce-padded number. Once the commitments have been distributed, the parties open the commitments by publishing the nonce and the number. The numbers are combined in some previously agreed suitable fashion such as adding them ... 7 The interesting property for the one time pad is that every plausible plaintext (given the length constraint, i.e. of same length as the ciphertext, maybe including some padding) has a corresponding key which produces a certain ciphertext. As mentioned in the comment by CodesInChaos, this key can be retrieved by simply XORing both plaintext and ciphertext ... 7 How long are parameters used for? Usually$g$and$p$are kept static for a very long time indeed. In fact, the values to use are actually written in to standards. See here for an example. Those were values standardised ten years ago. So the answer is basically decades. The impossibility of brute force Let's suppose that I as an attacker decide I'm going ... 7 As long as you use a secure padding mode (i.e. -pkcs or -oaep, not -raw). The default padding mode for openssl rsautl is -pkcs (i.e. PKCS#1 v1.5), so you should be OK. That said, OAEP is recommended over PKCS#1 v1.5 padding, so you might want to use the -oaep switch. 7 I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time" Using a perfectly random key which is as long as the message itself, not a pseudo-random key, cannot be broken no matter how fast the attacker's computer is. This scheme is called one-time-pad and its security is guaranteed by information theory ... 7 As pointed in this comment, using a huge random key for a sound block cipher is an excellent defense to resist ASIC/GPU attacks. Each bit added doubles the effort required. If an adversary was able to build$10^{12}$ASICs each capable of testing$10^{12}\$ keys per second, odds of finding a 128-bit key by brute force running that for a decade are less than ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
Erdős-Szekeres empty pseudoconvex $k$-gons - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T06:55:41Z http://mathoverflow.net/feeds/question/88480 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88480/erds-szekeres-empty-pseudoconvex-k-gons Erdős-Szekeres empty pseudoconvex $k$-gons Joseph O'Rourke 2012-02-15T01:56:39Z 2012-02-15T01:56:39Z
I am wondering if the Erdős-Szekeres empty convex $k$-gon question has a different answer if convexity is replaced by a pseudoline-version of convexity.

The empty convex $k$-gon question is a variant on the Happy Ending Problem. The last remaining case, $k=6$, was settled about four years ago. It is now known that, although there arbitarily large point sets in the plane with no empty convex heptagon, every sufficiently large set contains an empty convex hexagon.

Here is my attempt to generalize this to pseudolines. An arrangement of pseudolines is a collection of curves each pair of which intersects in exactly one point, at which they cross. There are nonstretchable pseudoline arrangements, i.e., those not combinatorially equivalent to any straight-line arrangement. Here's one:

         (Image by David Eppstein)
 In fact, there are many more pseudoline arrangements— $2^{\Omega(n^2)}$, than straight-line arrangements— $2^{O(n \log n)}$, for $n$ lines and simple arrangements.

All the above are facts. Caveat: my attempt at defining convexity in this context might not make sense. Given $n$ points in the plane, say that they contain an empty pseudoconvex $k$-gon if

 there is an arrangement $\cal{A}$ of $\binom{n}{2}$ pseudolines through the $n$ points.

 there is an empty $k$-gon $K$, a region of the plane bounded by $k$ pseudolines containing no points in its interior.

 $K$ is convex in the sense that for any two additional points $a,b$ inside $K$, one can find a pseudoline through $a,b$ compatible with the arrangement $\cal{A}$, such that the pseudosegment $ab \subset K$.

Assuming this definition is not inconsistent, does the Erdős-Szekeres empty convex $k$-gon question have a different answer? For example, perhaps every sufficiently large point set always has a pseudoconvex heptagon?

Aside from this question, I would be interested in learning of convexity definitions analogous to what I tried to define above. Thanks for pointers/ideas!


text:
# AP Calc BC in a week - Part 2

## Introduction

Today we'll be doing:

• 4K Motion along a curve: Velocity and Acceleration Vectors
• 4N Slope of a Polar Curve
• 5C Integration by Partial Fractions
• 5D Integration by Parts

Let's start!

## 4K Motion along a curve: Velocity and Acceleration Vectors

So we've got a pair of parametric equations $$x(t)$$ and $$y(t)$$, and a point $$P$$ moves along the curve. At a given $$t$$, $$P$$ will be at $$(x,y)$$, where the x and y coordinates conveniently coincide with their functions at the given $$t$$.

### Position Vector

That means that a vector can be drawn from the origin to $$(x,y)$$, and this will be called the position vector: $$\vec{R} = \langle x,y \rangle$$

### Velocity Vector

Thus a velocity vector can be derived from $$\vec{R}$$ by finding its derivative: $$\vec{v} = \frac{d\vec{R}}{dt} = \langle \frac{dx}{dt}, \frac{dy}{dt} \rangle$$

The slope is: $$\frac{dy}{dx} = \frac{\frac{dy}{dt}}{\frac{dx}{dt}}$$ Which we defined yesterday as the derivative of a parametric function!!

The magnitude is simple Pythagoras: $$|v| = \sqrt{(\frac{dx}{dt})^2+(\frac{dy}{dt})^2}$$

If you draw the velocity vector beginning at $$P$$, the slope gives you the direction and the magnitude gives you the speed of the velocity of the moving point $$P$$.

### Acceleration Vector

The acceleration vector can likewise be derived from the velocity vector by differentiating it: $$\vec{a} = \frac{d\vec{v}}{dt} = \frac{d^2\vec{R}}{dt^2} = \langle \frac{d^2x}{dt^2}, \frac{d^2y}{dt^2} \rangle$$

The magnitude can be found with good 'ol Pythagoras again: $$|a| = \sqrt{(\frac{d^2x}{dt^2})^2+(\frac{d^2y}{dt^2})^2}$$

### Take-home message

• Position vector is just a vector from the origin to $$(x,y)$$. $$x$$ and $$y$$ conveniently correspond to the parametric equations.
• Velocity vector is just the derivative of the position vector. Just differentiate $$x$$ and $$y$$ in the position vector.
• Acceleration vector is just the derivative of the velocity vector. Just differentiate $$\frac{dx}{dt}$$ and $$\frac{dy}{dt}$$ in the velocity vector.
• To find the slope, $$\frac{dy}{dx}=\frac{y'(t)}{x'(t)}$$
• To find the magnitude, just use good 'ol Pythagoras

## 4N Slope of a Polar Curve

To find the slope of a polar curve, first you make it parametric, then you can easily differentiate that. There's a super-complicated formula that you might as not even try to remember.

Say you have a polar function $$r=f(\theta)$$, then it can be expressed parametrically as $$x=r\cos\theta=f(\theta)\cos\theta$$ and $$y=r\sin\theta=f(\theta)\sin\theta$$

Then, you can simply differentiate these two (product rule) to get $$\frac{dx}{d\theta}$$ and $$\frac{dy}{d\theta}$$: $$\frac{dx}{d\theta} = f'(\theta)\cos\theta - f(\theta)\sin\theta$$ $$\frac{dy}{d\theta} = f'(\theta)\sin\theta + f(\theta)\cos\theta$$

Then you just divide those parametric equations by doing $$\frac{dy}{dx} = \frac{\frac{dy}{d\theta}}{\frac{dx}{d\theta}}$$ which you can do yourself so I'm not going to show you. (Also the result is that long complicated formula that you might as well not memorize)

The given example questions are simple stuff like find the slope of a function at a given $$\theta$$, simple stuff that we've been doing for the entirety of differential calculus, so there should be no problem.

### Take-home message

• Turn the polar function into parametric equations and differentiate each, and divide $$x'(\theta)$$ by $$y'(\theta)$$ and you've got your $$\frac{dy}{dx}$$ !

## 5C Integration by Partial Fractions

Ooh integral calculus now.

So the main concern here is splitting a complicated polynomial fraction like $$\frac{x^2-2x-8}{x^3+2x^2-3x}$$ into many less complicated fractions so we can easily integrate it. Also if you have an improper fraction, split it into proper fractions before you do this method, since this method only works with proper fractions.

First, we have to factor the denominator: $$\frac{x^2-2x-8}{x(x-3)(x+1)}$$ This will be set to be equal to three partial fractions, one for each term, in the form $$\frac{A}{x-a}$$: $$\frac{A}{x}, \frac{B}{x-3}, \frac{C}{x+1}$$

This results in $$\frac{x^2-2x-8}{x(x-3)(x+1)} = \frac{A}{x} + \frac{B}{x-3} + \frac{C}{x+1}$$ which can also be expressed as $$x^2-2x-8 = A(x-3)(x+1) + Bx(x+1) + Cx(x-3)$$

Then there are two methods to find $$A$$, $$B$$, and $$C$$.

### Method 1

The first method is to expand and then combine the second equation. $$x^2-2x-8 = A(x-3)(x+1) + Bx(x+1) + Cx(x-3)$$ $$x^2-2x-8 = Ax^2 + -2Ax + -3A + Bx^2 + Bx + Cx^2 + -3Cx$$ $$x^2-2x-8 = (A+B+C)x^2 + (-2A+B-3C)x -3A$$

Then you can equate the coefficients and then use simultaneous equations to solve for $$A$$, $$B$$, and $$C$$.

### Method 2

The second method is a lot easier. In the first equation, $$\frac{x^2-2x-8}{x(x-3)(x+1)} = \frac{A}{x} + \frac{B}{x-3} + \frac{C}{x+1}$$, there are some illegal values, namely $$x=0$$, $$x=3$$, and $$x=-1$$. However, these values must still hold for the second equation, and in fact we can plug them in to that equation and it'll remove some terms, making it a lot easier to find $$A$$, $$B$$, and $$C$$.

Try it! Plug in $$x=0$$, $$x=3$$, and $$x=-1$$ into $$x^2-2x-8 = A(x-3)(x+1) + Bx(x+1) + Cx(x-3)$$ and get your $$A$$, $$B$$ and $$C$$ and compare the results with Method 1! They should be the same.

### After A, B and C

Now just plug in $$A$$, $$B$$, and $$C$$, and you've got your partial fractions!

### Take-home message

• We're splitting complicated fractions into smaller ones
• Make sure it's a proper fraction
• Factor out the denominator and equate the whole fraction to a number of fractions for each term in the denominator
• Multiply everything by the denominator
• Find the numerators by expansion and combination
• Or by using the values of $$x$$ where the fractions would be undefined

## 5D Integration by Parts

### Derivation

Okay... so this is basically the product rule for integrals. First we'll derive the Parts formula (so that you don't have to memorize it):

We start off with the Product Rule: $$\frac{d}{dx}(uv) = u\frac{dv}{dx} + v\frac{du}{dx}$$ Which simplifies to: $$d(uv) = udv + vdu$$ Rearrange: $$udv = d(uv) - vdu$$ And integrate: $$\int u dv = uv - \int v du$$ This is the Parts formula.

### Usage

Basically we have to split the product that is being integrated into a $$u$$ and a $$dv$$. Then we would differentiate the $$u$$ to get a $$du$$ and integrate the $$dv$$ to get a $$v$$. That means that $$dv$$ better be easy to integrate and $$\int v du$$ better be easy to integrate as well.

Example: $$\int x \sin x dx$$ $$u = x, du = dx$$ $$dv = \sin x dx, v = -\cos x$$ $$\int x \sin x dx = x \times -\cos x - \int -\cos x dx$$

Sometimes Parts will need to be repeated, for example: $$\int x^2 \sin x dx$$ $$u = x^2, du = 2x dx$$ $$dv = \sin x dx, v = -\cos x$$ $$\int x^2 \sin x dx = x^2 \times -\cos x - \int -\cos x \times 2x dx$$ And we just do Parts again on the second integral on the right hand side.

### Tic-Tac-Toe Method

This method looks useful, but I can't get it straight (I feel like I'm going to lose track of the lines) (Hahaha Lines? Straight? Get it?) so I'm just going to skip this and if I ever get something like $$u=x^4$$ then I'll just do Parts over and over again. Hopefully I never have to deal with $$u=x^{10}$$.

### LIATE

This isn't from the book, but I found it on Wikipedia and it looks absolutely fabulous!

Basically this says that the highest thing on the list should be $$u$$, and here is the list:

1. L - Logarithmic
2. I - Inverse Trig
3. A - Algebraic
4. T - Trig
5. E - Exponential

Conversely the lowest thing on the list should be $$dv$$.

If LIATE is hard to remember, you can also remember it as DETAIL, where D means that this is better for dv.

### Take-home message

• Derive the Parts formula $$\int u dv = uv - \int v du$$ from the Product rule $$\frac{d}{dx}uv = u\frac{dv}{dx} = v\frac{du}{dx}$$
• Split your integral into $$u$$ and $$dv$$ according to LIATE (or DETAIL)

## Conclusion

Still good. Maybe doing some practice problems is a good idea.

I think at the end of the week I'll compile all the take-home messages into one post.

Next time we'll be doing:

• 6C Integrals involving Parametrically Defined Functions
• 7C Arc Length
• 7D Improper Integrals
• 8B Motion along a Plane Curve

Stay tuned!

2016-03-21 Paul Elder


text:
# Calendar of Events

## Events Calendar

### Modeling the initial condistions of heavy ion collisions

Date and Time: Thursday, January 24, 2019, 10:30am -
Location: Room 112

Speaker: Doug Wertepny (Ben Gurion University of the Negev)

Heavy ion collisions are a topic of intense research due to the fact that is is one of the few situations in nature where a Quark Gluon Plasma (QGP) can form. Theoretical studies of these are complicated by the fact that at various stages of the process different physical phenomenon take over and dominate. In order to fully understand heavy ion collisions one must have a detail understanding of the early time dynamics. We model these initial conditions by using the saturation/Color Glass Condensate framework, which takes into account the initial high energy scattering. While this formalism has been used to calculate the initial gluon distributions to reasonable success we are currently expanding this to include the initial distribution of quarks and anti-quarks with the overall goal of being able to incorporate these into the initial conditions as well. Using these improved initial conditions we hope to be able to calculate various observables in a consistent manner, such as correlations between hadrons and charge dependence.

Extra Info:


text:
# [CRV19] The First Fully Polynomial Stabilizing Algorithm for BFS Tree

Revue Internationale avec comité de lecture : Journal Information and Computation, vol. 265, pp. 26-56, 2019, (doi:https://doi.org/10.1016/j.ic.2019.01.005)

Mots clés: Distributed systems, Fault-tolerance, Stabilization, Spanning tree construction

Résumé: The construction of a spanning tree is a fundamental task in distributed systems which allows to resolve other tasks (i.e., routing, mutual exclusion, network reset). In this paper, we are interested in the problem of constructing a Breadth First Search (BFS) tree. Stabilization is a versatile technique which ensures that the system recovers a correct behavior from an arbitrary global state resulting from transient faults. A \emph{fully polynomial} algorithm has a round complexity in $O(d^a)$ and a step complexity in $O(n^b)$ where $d$ and $n$ are the diameter and the number of nodes of the network and $a$ and $b$ are constants. We present the first fully polynomial stabilizing algorithm constructing a BFS tree under a distributed daemon. Moreover, as far as we know, it is also the first fully polynomial stabilizing algorithm for spanning tree construction. Its round complexity is in $\Theta(d^2)$ and its step complexity is in $O(n^6)$.

Collaboration: Laboratoire MIS

# BibTeX

 @article { CRV19, title = "{The First Fully Polynomial Stabilizing Algorithm for BFS Tree}", author = "A. Cournier and S. Rovedakis and V. Villain", journal = "Information and Computation", year = 2019, volume = 265, pages = "26-56", doi = "https://doi.org/10.1016/j.ic.2019.01.005", }


text:
• Post author:

In this article I’ll briefly explain how you can rotate an object, using Unity, in order for it to “look” at the mouse position.

### TL;DR

Here’s the code snippet which will make the player transform point towards the mouse position. Please read below if you’re interested in how this works.

private void PointToMouse(Transform player)
{
var mouseScreenPos = Input.mousePosition;
var startingScreenPos = mainCamera.WorldToScreenPoint(player.position);
mouseScreenPos.x -= startingScreenPos.x;
mouseScreenPos.y -= startingScreenPos.y;
var angle = Mathf.Atan2(mouseScreenPos.y, mouseScreenPos.x) * Mathf.Rad2Deg;
player.rotation = Quaternion.Euler(new Vector3(0, 0, angle));
}

### Explanation

Let’s start with the definition Math.Atan2 that you can find in the Unity documentation:

Returns the angle in radians whose Tan is y/x.
Return value is the angle between the x-axis and a 2D vector starting at zero and terminating at (x,y).

And that’s why, at line 7, we provide the x and y of the mouse position (multiplying everything by the radians-to-degrees conversion constant). But where does all this come from?

To understand that, we need to dust off some old mathematics memories and make use of some linear equation formulas. And so, given two lines:

$\displaystyle y_1 = m_1x_1 + q_1 \\ y_2 = m_2x_2 + q_2$

and their respective slopes m1 and m2, the angle between them is given by:

$\displaystyle \varphi = \arctan \left|\frac{m_1 + m_2}{1 + (m_1m_2)} \right|$

All right but, how do we go from the formula above to the Unity’s one which basically is:

$\displaystyle \tan (\varphi) = \left|\frac{y_2}{x_2}\right| \Rightarrow \varphi = \arctan \left|\frac{y_2}{x_2} \right|$

Simply by considering the first line as the x-axis, and the second one (the one pointing to the mouse) as passing from zero. That gives us the following:

$\displaystyle y_1 = m_1x_1 = 0 \Rightarrow m_1 = 0 \\ \\ y_2 = m_2x_2 \Rightarrow m_2 = \frac{y_2}{x_2}$

And by replacing slopes with their respective values, we end up with:

$\displaystyle \varphi = \arctan \left|\frac{0 + \frac{y_2}{x_2}}{1 + (0\frac{y_2}{x_2})} \right| \Rightarrow \varphi = \arctan \left|\frac{y_2}{x_2} \right|$

### Applying the simplified formula in Unity

In order to use this simplified version in Unity, we need to apply some tweaks. The easiest way to accomplish this is to move from the world-space (measured in units) to the screen-space (measured in pixels). The screen-space comes very handily in this case because it emulates the “first quadrant” of a “Cartesian plane”, where all the x and y are positive. Find more info here.

In order to work on the screen-space, we fetch the mouse position using Input.mousePosition (line 3), and then we have to transform the player position from world to screen coordinates with mainCamera.WorldToScreenPoint(player.position) (line 4). After that, we just need to translate the points (lines 5/6) in order to have the player in (0,0) (remember that Unity’s formula implies the first line to be the x-axis).

Once done, we should end up in a situation like this, and therefore being able to apply our simple formula to retrieve the correct angle and then apply a rotation to the player’s transform (line 8):

### Wrapping up

Unity is a very well done game engine and it perfectly suits both experts and beginners users by hiding some of the complexity involved in the game development world. But I think that sometimes it is worth to understand what’s really going on behind those very simple methods. Whether it is just for curiosity or professional needs, it should help us improve in what we do.


text:
# Vector representation in dual space

I'm new to tensor analysis, and came across the topic of vectors and duals, and faced a massive confusion. Are vectors and duals different representations of the same object ? I had another doubt regarding this, as follows.

Let us say, we have a set of basis vectors $$u_1,u_2 = (2,1), (1,1)$$

Suppose we have a vector $$V$$ in this space, given by $$V = 2u_1 +3u_2$$.

As I've read, the components here are the 'contravariant' components of the Vector. However, we could express the same vector in its dual space, using the 'covariant' components. In order to do this, we would need to the 'dual-basis' Using $$u^j u_i = \delta^i_j$$ in matrix notation, i've calculated the dual basis vectors to be $$u^1,u^2 = (1,-1), (-1,2)$$

My question is, how do I express the vector $$V$$ in this dual basis. Do I use the simple change of basis matrix ? Moreover, the coefficients that I get, in this case, are these the 'covariant' coefficients ? I've seen expressions like this, $$x_i = V.u_i$$

This doesn't make sense to me, as $$V.u_i = x^iu_i.u_i = x^i$$

Can someone point out where I've made a mistake in this, and how can I correctly express the same vector in the co-variant and contra-variant way?

• Dual vectors (also called one forms) are not the same objects as vectors. Why do you assume that an object $V$ given to be a vector "can be represented" using a dual basis? While something similar might be possible, it doesn't have to be the case always. – newtothis Jun 16 at 7:08

Confusion about this goes on and on and on. And I've seen it go on for more than forty years. The word "dual" and the words "contravariant"/"covariant" correspond to different things. The problem is that in finite dimension, and working in coordinates, dual spaces look so much as the original space $$V$$ that there is a risk of confusion.

## Dual Space

Dual space of a given linear space $$V$$: $$\begin{array}{cccc} \omega: & V & \rightarrow & \mathbb{R}\\ & x & \mapsto & \omega\left(x\right) \end{array}$$ The space of all these things is called the dual space of $$V$$: $$V^{*}:=\left\{ \omega:V\rightarrow\mathbb{R}/\omega\textrm{ is linear}\right\}$$ Here you have two different spaces, so it's obvious you can choose any basis you want to expand your linear forms. Why not choose the one in which the action of the $$\omega$$'s on the vectors is simplest?: $$\alpha_{i}\left(e_{j}\right)=\delta_{ij}$$ This is called the dual basis.

## Scalar product

Scalar product on a given linear space $$V$$: $$\begin{array}{cccc} \left\langle \:,\:\right\rangle : & V\times V & \rightarrow & \mathbb{R}\\ & \left(x,y\right) & \mapsto & \left\langle x,y\right\rangle \end{array}$$ Here you have one space $$V$$, and one space only. Perhaps you do not care to consider linear mappings on the scalars. This context is more typical when you're thinking geometrically, and you wish to talk about distances and angles.

And the problem when you have a scalar product arises because you would like to expand vectors in terms of their projections on different 1-dim subspaces: $$x=\left\langle x,e_{i}\right\rangle e_{i}\:\textrm{wrong!!!}$$ This formula doesn't work when your basis is not orthonormal. If you just naively project your vector on the basis, you get, $$\left\langle x,e_{j}\right\rangle =\left\langle x^{i}e_{i},e_{j}\right\rangle =x^{i}\left\langle e_{i},e_{j}\right\rangle =x^{i}g_{ij}$$ This is not your contravariant coordinate --the coordinate $$x^j$$ such that, $$x=x^{j}e_{j}$$ And the reason why it's not is that your basis is not orthonormal: $$\left\langle e_{i},e_{j}\right\rangle =g_{ij}\neq\delta_{ij}$$ What you need is, so to speak, a basis that is "orthonormal with respect to $$\left\{ e_{i}\right\}$$" Enough of the formalism has been developed that I don't need to repeat. Let's go to your example. The basis you propose is not orthonormal: $$\left\langle u_{i},u_{j}\right\rangle =g_{ij}=\left(\begin{array}{cc} 5 & 3\\ 3 & 2 \end{array}\right)$$ Let's call that the "covariant basis". The "contravariant basis" is: $$u^{1}:=\left(a_{1},a_{2}\right)$$ $$u^{2}:=\left(b_{1},b_{2}\right)$$ Solving for, $$\left(a_{1},a_{2}\right)\cdot\left(2,1\right)=1$$ $$\left(a_{1},a_{2}\right)\cdot\left(1,1\right)=0$$ and, $$\left(b_{1},b_{2}\right)\cdot\left(2,1\right)=0$$ $$\left(b_{1},b_{2}\right)\cdot\left(1,1\right)=1$$ You can easily prove,

$$u^{1}=\left(1,-1\right)$$ $$u^{2}=\left(-1,2\right)$$ Let us see that this is the proper contravariant basis. We must check that the vector $$v$$ that you provide can actually be expanded in terms or projections on the basis vectors, but by introducing the contravariant basis. That is,

$$v\overset{?}{=}\left\langle v,u_{1}\right\rangle u^{1}+\left\langle v,u_{2}\right\rangle u^{2}$$ What is $$v$$?: $$v=2u_{1}+3u_{2}=2\left(2,1\right)+3\left(1,1\right)=\left(7,5\right)$$ What are the projections on the given basis?: $$\left\langle v,u_{1}\right\rangle =\left(7,5\right)\cdot\left(2,1\right)=19$$ $$\left\langle v,u_{2}\right\rangle =\left(7,5\right)\cdot\left(1,1\right)=12$$ Check: $$\left\langle v,u_{1}\right\rangle u^{1}+\left\langle v,u_{2}\right\rangle u^{2}=19\left(1,-1\right)+12\left(-1,2\right)=\left(7,5\right)$$ Now let's do the check by using the contravariant basis/covariant coordinates as the reference: $$\left\langle v,u^{1}\right\rangle =\left(7,5\right)\cdot\left(1,-1\right)=2$$ $$\left\langle v,u^{2}\right\rangle =\left(7,5\right)\cdot\left(-1,2\right)=3$$ And, $$v\overset{?}{=}\left\langle v,u^{1}\right\rangle u_{1}+\left\langle v,u^{2}\right\rangle u_{2}$$ $$\left\langle v,u^{1}\right\rangle u_{1}+\left\langle v,u^{2}\right\rangle u_{2}=2\left(2,1\right)+3\left(1,1\right)=\left(7,5\right)$$ It checks. Same vector, two different expansions in terms of different bases --and projections.

I hope that clarified the question a little bit.

• Thank you so much, this is exactly what I was looking for. However, there is one small doubt, as to a similar question regarding the geometrical picture of this. Would you mind if I ask it to you ? – Nakshatra Gangopadhay Jun 17 at 16:27
• what I understand from most of the comments is that the confusion arises because of something called the reciprocal basis, which mimics the dual space, but unlike the dual space which is a different object, this reciprocal space is similar to our original vector space. Since the components in reciprocal space and dual space match exactly, we tend to call this the dual space instead, not knowing they are separate things. Is that right ? – Nakshatra Gangopadhay Jun 17 at 16:32
• Sometimes you have a dual space in its own right because the linear forms that you're considering are very different things from your vectors. Typical example: functional spaces in quantum mechanics. If they're infinitely generated, it's particularly important to distinguish $V$ from its dual. If you just have one $V$ and a scalar product, and finite dimension, and your main concern are distances/angles, then you can relax about the whole thing and say that every vector $u$ has a unique linear form $\omega$ such that $\omega_{u}\left(x\right)=\left\langle u,x\right\rangle$. – joigus Jun 17 at 19:04

Are vectors and duals different representations of the same object ?

Not generally. Duals are linear functionals of vectors, i.e. they are objects that take vector and produce real number, so they are different beasts.

But they do form vector space in their own right with same dimensionality as the original and every two vector spaces with same dimensionality are isomorphic to each other, meaning we can map each element of original vector space to its dual space and vice versa.

Having basis in original vector space $$e_b$$, we can find dual basis $$e^a$$ in dual space by requirement, that it is set of dual vectors which takes one basis elements and produces 1 and 0 for others, i.e. $$e^a(e_b)=\delta^a_b.$$ This defines an isomorphism between the two spaces (by identifying $$e^0$$ with $$e_0$$, etc.). Its not canonical though, because starting with another basis $$e'_a$$ would result in different isomorphism.

However, we could express the same vector in its dual space, using the 'covariant' components

This is incorrect. If we were to express vector in its dual space, then we are not expressing the vector, but mapping to another vector in different vector space. This is moreover not unique, and different basis would result in different dual vector to which it is mapped.

What different expression of the same vector means is that we are decomposing it relative to two different basis in the same vector space.

To define covariant and contravariant components, we first need canonical identification of vector space and its dual. This is usually achieved by metric and isomorphism is given by $$e^a=g(e_a,.),$$ i.e. we identify basis vector $$e_a$$ with dual vector $$e^a$$, that produces from vector $$v$$ the same number as operation $$g(e_a,v)$$.

Having a basis $$e_a$$ in vector space, canonical isomorphism that maps this basis into basis $$e^b$$ in dual space (this is not necessarily dual basis as defined in the first section!), we can define new basis $$e'_c$$ in the original vector space, by requirement, that $$e^b(e'_c)=\delta^b_c.$$

The result is, that the components of vector $$v$$ in this dual basis $$e'_b$$ will be the same as components of the dual vector $$\alpha$$ identified with $$v$$ by our isomorphism when expressed in coordinates $$e^a$$ that are identified with our original basis vectors $$e_a$$, i.e.: $$\alpha=\alpha_a e^a$$ $$e^a=g(e_a,.)$$ $$v=v^a e_a = v^b e'_b$$ $$v^b =\alpha_b$$ $$e^a(e'_b)=\delta^a_b$$ $$e^a(e_b)=g_{ab}$$ where $$\alpha \leftrightarrow v$$ by the isomorphism.

Yes, it is a little confusing.

EDIT

...can you tell me how to prove that the components in this third basis are the same as the components in the covector basis ?

Its property of isomorphism given by dual basis. The dual basis to $$e^b$$ is $$e_b$$ and the isomorphism maps $$e^0$$ to $$e_0$$ and analogically for every other index. For general covector the isomorphism is a map $$\Phi: \alpha \leftrightarrow v,$$ and on the basis we know that $$e_b=\Phi(e^b).$$ The map $$\Phi$$ is linear, since it is a morphism and preserves structure, i.e $$v=\Phi(\alpha)=\Phi(\alpha_a e^a)=\alpha_a\Phi( e^a)=\sum_a \alpha_a e_a,$$ i.e. $$v^a=\alpha_a$$ in dual basis.

For comparison, the isomorphism given by metric is $$\Phi_g: \alpha \leftrightarrow v,$$ and on the basis we know that $$f_b=\Phi_g(e^b).$$ Now, the metric is expressed as $$g=g^{ab}e_a \otimes e_b,$$ where $$e_a$$ is dual basis to $$e^a$$. It needs to be dual basis, because only then the formula $$g(\alpha,\beta)=g^{ab}\alpha_a\beta_b$$ holds, since $$g(\alpha,\beta)=\alpha_a\beta_bg(e^a,e^b)=\alpha_a\beta_bg^{cd}e_c(e^a)e_d(e^b)=\alpha_a\beta_bg^{cd} \delta^a_c\delta^b_d.$$ So if it would not be true that $$e_a(e^b)=\delta_a^b$$, then additional terms would appear.

Next we need to determine how $$f_b$$ is expressed in the dual basis. Acting with $$f_b$$ on basis covectors $$e^a$$ we get $$f_b(e^a)\equiv g(e^b,e^a)=g^{ba},$$ i.e the components of $$f_b$$ with respect to basis $$e^a$$ are $$g^{ba}$$. The first equality is simply the definition of canonical isomorphism $$e_a\leftrightarrow f^a=g(e_a,.)$$.

Now, for the general vector: $$v=\Phi_g(\alpha)=\Phi_g(\alpha_a e^a)=\alpha_a\Phi_g( e^a)=\alpha_a f_a=\alpha_a g^{ab}e_b.$$ I.e. now the componets are $$v^b=\alpha_a g^{ab},$$ which is well known raising of indexes.

• I'm fairly new to this subject, so I'm a little slow at grasping the notations. But based on this, what I understand is, vectors and duals are different, and a certain vector corresponds to a certain dual in the dual space. However, we can define a third basis in the original vector space, which would relate to the dual of the original vector, and representing the original vector in this new basis would be similar to finding the dual. This is what we mean by the covariant component. Since the new basis is related to the dual, the component of this basis is the co-variant component. – Nakshatra Gangopadhay Jun 16 at 7:56
• Sorry about the sloppyness. – Nakshatra Gangopadhay Jun 16 at 7:56
• @NakshatraGangopadhay sorry, I cannot make out if you understood it or not. This whole thing is quite nuanced and proper terminology needs to be used. For example "Since the new basis is related to the dual", no it is related to one particular basis in dual space, not dual that you first claimed to be covector identified with some vector. The third basis is dual basis of the basis in covector space that is identified with original basis in original space. – Umaxo Jun 16 at 8:05
• @NakshatraGangopadhay Anyway, while I disagree with Vincent that there is no third basis or covariant/contravariant components, I do think that this business with covariant/contravariant components is needlessly confusing and it would be much easier if we just forgot it and used simple maps between space and dual space instead of this basis shenanigans. – Umaxo Jun 16 at 8:12
• @Umaxo okay so, components of the vector in this third basis, which is dual of the covector basis, which in turn is the dual of the original basis, are the same components of the dual to the original vector. However, since this maps back to our original space, we can call this the co-variant component of the original vector. Is this correct ? – Nakshatra Gangopadhay Jun 16 at 8:30

You have several confusions here.

## 1.

The terms "contravariant" and "covariant" are simply wrong. There is no such thing as contravariant and covariant components of the same vector. Many texts do not give a proper treatment of this (which I think is important to know). What we are actually dealing with are objects known as covectors, which are not quite the same as vectors.

Consider a vector space $$V$$ over a field $$F$$. The field arises because $$V$$ has the operation of scalar multiplication such that for any $$v \in V$$ and $$k \in F$$, we have $$kv \in V$$. In other words, $$F$$ is just the set of scalars used in scalar multiplication. In practice, $$F$$ is usually $$\mathbb{R}$$ or $$\mathbb{C}$$.

If we define a basis $$\mathbf{e}_i$$ on $$V$$, then for every $$v \in V$$ there exists unique coefficients $$v^i$$ such that $$v = v^i \mathbf{e}_i$$. The coefficients $$v^i$$ are the components the vector. Now we introduce the dual space $$V^*$$ which is the set of all linear maps from $$V$$ to $$F$$. If $$\omega \in V^*$$, then we have $$\omega(v) \in F$$. As long as $$V$$ is finite-dimensional, elements of $$V$$ are also linear maps from $$V^*$$ to $$F$$, so we also have $$v(\omega) \in F$$.

The elements of $$V^*$$ are known as covectors.

Now we define the dual basis $$\mathbf{e}^i$$, which is also often (incorrectly) referred to as the contravariant basis, by $$\mathbf{e}^i (\mathbf{e}_j) = \delta^i_j$$

Therefore we can also decompose a covector $$\omega$$ into its components as $$\omega = \omega_i \mathbf{e}^i$$. With that, we have $$\omega(v) = \omega_i v^i$$

The metric tensor $$g$$ can be used to "convert" any vector to a corresponding covector. If we have a vector $$v$$, its corresponding covector is $$g(v) = g_{ij} \mathbf{e}^i \otimes \mathbf{e}^j (v^k \mathbf{e}_k) = g_{ij} v^k \mathbf{e}^i \delta^j_k = (g_{ij} v^j) \mathbf{e}^i$$

Therefore we see that the components of the corresponding covector is $$g_{ij} v^j$$. This is what you were trying to do. You are not representing the same vector with different components. What you are really doing is finding the components of the corresponding covector in the dual space. Vectors have components ("contravariant"), and covectors have components ("covariant"). That's it.

In Euclidean space with Cartesian coordinates, there is no difference between vectors and covectors because the components of the metric tensor is just the identity matrix. Only in this special case, vectors and covectors have the same components.

## 2.

Let us say, we have a set of basis vectors $$u_1,u_2 = (2,1), (1,1)$$

This is also wrong. A basis vector in its own coordinate system is always $$(1,0)$$ or $$(0,1)$$. If it is not, then it means that it is defined relative to some other "background" coordinate system. Therefore, you need to be careful when raising and lowering indices because the components of $$g$$ depend on the coordinate system. You need to make sure that everything is expressed in the same coordinate system.


text:
# Stereotype space

In functional analysis and related areas of mathematics stereotype spaces are topological vector spaces defined by a special variant of reflexivity condition. They form a class of spaces with a series of remarkable properties, in particular, this class is very wide (for instance, it contains all Fréchet spaces and thus, all Banach spaces), it consists of spaces satisfying a natural condition of completeness, and it forms a closed monoidal category with the standard analytical tools for constructing new spaces, like taking closed subspace, quotient space, projective and injective limits, the space of operators, tensor products, etc.

Mutual embeddings of the main classes of locally convex spaces

## Definition

A stereotype space[1] is a topological vector space over the field of complex numbers[2] such that the natural map into the second dual space

is an isomorphism of topological vector spaces (i.e. a linear and a homeomorphic map). Here the dual space is defined as the space of all linear continuous functionals endowed with the topology of uniform convergence on totally bounded sets in X, and the second dual space is the space dual to in the same sense.

The following criterion holds:[1] a topological vector space is stereotype if and only if it is locally convex and satisfies the following two conditions:

• pseudocompleteness: each totally bounded Cauchy net in converges,
• pseudosaturateness: each closed convex balanced capacious[3] set in is a neighborhood of zero in .

The property of being pseudocomplete is a weakening of the usual notion of completeness, while the property of being pseudosaturated is a weakening of the notion of barreledness of a topological vector space.

## Examples

Each pseudocomplete barreled space (in particular, each Banach space and each Fréchet space) is stereotype. A metrizable locally convex space is stereotype if and only if is complete. Each infinite dimensional normed space considered with the -weak topology is not stereotype. There exist stereotype spaces which are not Mackey spaces.

Some simple connections between the properties of a stereotype space and those of its dual space are expressed in the following list of regularities.[1][4] For a stereotype space

• is barreled has the Heine-Borel property;
• is quasibarreled in if a set is absorbed by each barrel, then is totally bounded;
• is a Montel space is barreled and has the Heine-Borel peoperty is a Montel space;
• is a space with a weak topology in every compact set is finite-dimensional;
• is separable in there is a sequence of closed subspaces of finite co-dimension with trivial intersection: .
• is a Pták space[7] in a subspace is closed if it has the closed intersection with each compact set ;
• is hypercomplete[8] in an absolutely convex set is closed if it has the closed intersection with each compact set .

## History

The first results on this type of reflexivity of topological vector spaces were obtained by M. F. Smith[9] in 1952. Further investigations were conducted by B. S. Brudovskii, [10] W. C. Waterhouse,[11] K. Brauner,[12] S. S. Akbarov,[1][4][13] and E. T. Shavgulidze.[14]

## Pseudocompletion and pseudosaturation

Each locally convex space can be transformed into a stereotype space with the help of the standard operations of pseudocompletion and pseudosaturation defined by the following two propositions.[1]

1. With any locally convex space , one can associate a linear continuous map into some pseudocomplete locally convex space , called pseudocompletion of , in such a way that the following conditions are fulfilled:

• is pseudocomplete if and only if is an isomorphism;
• for any linear continuous map of locally convex spaces, there exists a unique linear continuous map such that .

One can imagine the pseudocompletion of as the "nearest to from the outside" pseudocomplete locally convex space, so that the operation adds to some supplementary elements, but does not change the topology of (like the usual operation of completion).

2. With any locally convex space , one can associate a linear continuous map from some pseudosaturated locally convex space , called pseudosaturation of , in such a way that the following conditions are fulfilled:

• is pseudosaturated if and only if is an isomorphism;
• for any linear continuous map of locally convex spaces, there exists a unique linear continuous map such that .

The pseudosaturation of can be imagined as the "nearest to from the inside" pseudosaturated locally convex space, so that the operation strengthen the topology of , but does not change the elements of .

If is a pseudocomplete locally convex space, then its pseudosaturation is stereotype. Dually, if is a pseudosaturated locally convex space, then its pseudocompletion is stereotype. For arbitrary locally convex space the spaces and are stereotype.[15]

## Category of stereotype spaces

The class Ste of stereotype spaces forms a category with linear continuous maps as morphisms and has the following properties:,[1][13]

• Ste is pre-abelian;
• Ste is complete and co-complete;
• Ste is autodual with respect to the functor of passing to the dual space;
• Ste is a category with nodal decomposition: each morphism has a decomposition , where is a strong epimorphism, a bimorphism, and a strong monomorphism.

For any two stereotype spaces and the stereotype space of operators from into , is defined as the pseudosaturation of the space of all linear continuous maps endowed with the topology of uniform convergeance on totally bounded sets. The space is stereotype. It defines two natural tensor products

The following natural identities hold:[1]

As a corollary,

## Stereotype approximation property

A stereotype space is said to have the stereotype approximation property, if each linear continuous map can be approximated in the stereotype space of operators by the linear continuous maps of finite rank. This condition is weaker than the existence of the Schauder basis, but formally stronger than the classical approximation property (however, it is not clear (2013) whether the stereotype approximation property coincide with the classical one, or not). The following proposition holds:

• If two stereotype spaces and have the stereotype approximation property, then the spaces , and have the stereotype approximation property as well.[1]

In particular, if has the stereotype approximation property, then the same is true for and for .

## Applications

Being a symmetric monoidal category, Ste generates the notions of a stereotype algebra (as a monoid in Ste) and a stereotype module (as a module in Ste over such a monoid), and for each stereotype algebra the categories Ste and Ste of left and right stereotype modules over are enriched categories over Ste.[1] This distinguishes the category Ste from the other known categories of locally convex spaces, since up to the recent time only the category Ban of Banach spaces and the category Fin of finite-dimensional spaces had been known to possess this property. On the other hand, the category Ste is so wide, and the tools for creating new spaces in Ste are so diverse, that this suggests the idea that all the results of functional analysis can be reformulated inside the stereotype theory without essential losses. On this way one can even try to completely replace the category of locally convex spaces in functional analysis (and in related areas) by the category Ste of stereotype spaces with the view of possible simplifications – this program was announced by S. Akbarov in 2005[16] and the following results can be considered as evidences of its reasonableness:

• In the theory of stereotype spaces the approximation property is inherited by the spaces of operators and by tensor products. This allows to reduce the list of counterexamples in comparison with the Banach theory, where as is known the space of operators does not inherit the approximation property.[17]
• The arising theory of stereotype algebras allows to simplify constructions in the duality theories for non-commutative groups. In particular, the group algebras in these theories become Hopf algebras in the standard algebraic sense.[4][18]

## Notes

1. ...or over the field of real numbers, with the similar definition.
2. A set is said to be capacious if for each totally bounded set there is a finite set such that .
3. A locally convex space is called co-complete if each linear functional which is continuous on every totally bounded set , is automatically continuous on the whole space .
4. A locally convex space is said to be saturated if for an absolutely convex set being a neighbourhood of zero in is equivalent to the following: for each totally bounded set there is a closed neighbourhood of zero in such that .
5. A locally convex space is called a Pták space, or a fully complete space, if in its dual space a subspace is -weakly closed when it has -weakly closed intersection with the polar of each neighbourhood of zero .
6. A locally convex space is said to be hypercomplete if in its dual space every absolutely convex space is -weakly closed if it has -weakly closed intersection with the polar of each neighbourhood of zero .
7. It is not clear (2013) whether and coincide.

## References

• Schaefer, Helmuth H. (1966). Topological vector spaces. New York: The MacMillan Company. ISBN 0-387-98726-6.


text:
The purpose of this in-class lab is to practice conducting joint hypothesis tests of regression parameters in R. We will do this using t-tests and F-tests. The lab may be completed in your group, but each group member should submit their own copy. To get credit, upload your .R script to the appropriate place on Canvas.

## For starters

Open up a new R script (named ICL8_XYZ.R, where XYZ are your initials) and add the usual “preamble” to the top:

# Add names of group members HERE
library(tidyverse)
library(broom)
library(wooldridge)
library(car)
library(magrittr)
library(modelsummary)

We’ll use a data set on earnings and ability, called htv. The data set contains a sample of 1,230 workers.

df <- as_tibble(htv)

Check out what’s in the data by typing

datasummary_df(df)
datasummary_skim(df,histogram=FALSE)

The main variables we’re interested in are: wages, education, ability, parental education, and region of residence (ne, nc, west, and south).

### Create regional factor variable

Let’s start by creating a factor variable from the four regional dummies. Borrowing code from lab 6, we have:

df %<>% mutate(region = case_when(ne==1 ~ "Northeast",
nc==1 ~ "NorthCentral",
west==1 ~ "West",
south==1 ~ "South")) %>%
mutate(region = factor(region))

## Regression and Hypothesis Testing

Estimate the following regression model: $educ = \beta_0 + \beta_1 motheduc + \beta_2 fatheduc + \beta_3 abil + \beta_4 abil^2 + \beta_5 region + u$ Note that $$abil$$ is in standard deviation units. You will need to use a mutate() function to create $$abil^2$$ (not shown here). Call it abilsq. $$region$$ represents the factor variable you created above.1

est <- lm(educ ~ motheduc + fatheduc + abil + abilsq + region, data=df)
tidy(est)
modelsummary(est)

### t-test

1. Test the hypothesis that $$abil$$ has a linear effect on $$educ$$.

### F-test (single parameter)

1. Now test that $$motheduc$$ and $$fatheduc$$ have equal effects on $$educ$$. In other words, test $$H_0: \beta_1=\beta_2; H_a: \beta_1 \neq \beta_2$$. To do this, you will need to obtain $$se(\beta_1 - \beta_2)$$. Luckily, R will do this for you with the linearHypothesis() function in the car package:
linearHypothesis(est, "motheduc = fatheduc")

The resulting p-value is that of an F test, but one would get an identical result by using a t-test, since this is a simple hypothesis (see Wooldridge (2015), pp. 125-126).

### F-test (multiple parameters)

The p-values from the previous regression might indicate that the three region dummies don’t contribute to education.

1. Test the hypothesis that they don’t; i.e. test $H_0: \text{all region dummies}=0; \\ H_a: \text{any region dummy}\neq 0$

The code to do this again comes from the linearHypothesis() function. The syntax is to encolose each component hypothesis in quotes and then surround them with c(), which is how R creates vectors.

linearHypothesis(est, c("regionNortheast=0", "regionSouth=0", "regionWest =0"))

or, more simply,

linearHypothesis(est, matchCoefs(est,"region"))

Alternatively, you can perform the F-test as follows (no need to put this in your R-script; I’m just showing you how to do it “by hand”):

est.restrict <- lm(educ ~ motheduc + fatheduc + abil + abilsq, data=df)
Fstat.numerator   <- (deviance(est.restrict)-deviance(est))/3
Fstat.denominator <- deviance(est)/1222
Fstat <- Fstat.numerator/Fstat.denominator
p.value <- 1-pf(Fstat,3,1222)

This gives the exact same answer as the linearHypothesis() code.

# References

Wooldridge, Jeffrey M. 2015. Introductory Econometrics: A Modern Approach. 6th ed. Cengage Learning.

1. Here the notation of $$\beta_5 region$$ is not quite right. It more technically should be written $$\beta_5 region.NE + \beta_6 region.S + \beta_7 region.W$$, where each of the $$region.X$$ variables is a dummy. The way it is written above, $$\beta_5 region$$ implies that $$\beta_5$$ is a vector, not a scalar.↩


text:
2017-01-20

# Large Margin Classification

## optimization objective

modify the cost function curve for logistic regression into two straight line segments with one horizontal 0

Support vector machine:

cost function:
$min_{\theta}: C \left[ \sum_{i=1}^{m} y^{(i)}cost_1\left(\theta^T x^{(i)} \right) + \left(1-y^{(i)} \right)cost_0 \left(\theta^T x^{(i)} \right)\right] + \frac{1}{2}\sum_{j=1}^n \theta_j^2$

## large margin intuition

If $y=1$, we want $\theta^Tx \ge 1$ (not just 0). So if $\theta^Tx \ge 1$, the $cost_1$ function will return 0.
If $y=0$, we want $\theta^Tx \le -1$ (not just 0)

margin of the support vector machine or large margin classifier

The algorithm will give the largest margin to separate the positive and negative examples while setting C very large.
Using not too large C can ignore some outliner.

## mathematics behind large margin classification

norm: $\vert \vert u \vert \vert = \sqrt{u^Tu}$

### SVM decision boundary

vector $\theta$ is perpendicular to the decision boundary

# Kernels

Given $x$, compute new features depending on proximity to landmarks $l^{(1)},l^{(2)},l^{(3)}$. Landmarks are values of $x$.

Hypothesis: predict “1” when $\theta_0 +\theta_1 f_1 +...+\theta_n f_n \ge 0$

feature $f_1,f_2,f_3$:
$f_1 =similarity(x,l^{(1)}) = exp\left( - \frac{||x-l^{(1)}||^2}{2\sigma^2}\right)$

Similarity function is a kernel (the formula above is Gaussian kernel)

If $x \approx l^{(1)}$, $f_1 \approx 1$
If $x$ is far from $l^{(1)}$, $f_1 \approx 0$

As $\sigma^2$ increases, the similarity function tends to become sharper.

## choosing the landmarks

Where to get landmarks $l^{(1)},l^{(2)},l^{(3)},...$?

Use training examples for landmarks. So we will have m landmarks.
For training example $(x^{(i)},y^{(i)})$, we have m formula as:
$f_j^{(i)}=sim(x^{(i)},l^{(j)})$

$x^{(i)} \in \mathbb{R}^{n+1}$
$f^{(i)}=[f_0^{(i)},f_1^{(i)},f_2^{(i)},…,f_m^{(i)}]^T$
where $f_0^{(i)}=1$

## SVM with kernels

Hypothesis: given $x$, compute features $f \in \mathbb{R}^{m+1}$
Predict “$y=1$” if $\theta^T f \ge 0$ where $\theta \in \mathbb{R}^{m+1}$
Training:
$min_{\theta}: C\sum_{i=1}^{m} \left[ y^{(i)} cost_1(\theta^T f^{(i)})+(1-y^{(i)}) cost_0(\theta^T f^{(i)}) \right]+ \frac{1}{2}\sum_{j=1}^{m} \theta_j^2$

## SVM parameters

$C = 1/\lambda$:

Large $C$: Lower bias, high variance
Small $C$: higher bias, low variance

$\sigma^2$:

Large $\sigma^2$: Features $f_i$ vary more smoothly. higher bias, lower variance
Small $\sigma^2$: Features $f_i$ vary less smoothly. lower bias, higher variance

# SVMs in practice

Use SVM software package (e.g. liblinear, libsvm, …) to solve for parameters $\theta$.

Need to specify:

• choice of parameter $C$
• choice of kernel (similarity function):
• e.g. no kernel (“linear kernel”): predict “y=1” if $\theta^Tx \ge 0$ ( for large n, small m)
• Gaussian kernel (for small n, large m), need to choose $\sigma^2$; need to perform feature scaling before.

Not all similarity functions make valid kernels. Need to satisfy “Mercer’s Theorem” to make sure SVM packages’ optimizations run correctly and do not diverge.

Many off-the-shelf kernels available:

• polynomial kernel: e.g. $k(x,l)=(x^T l+a)^b$
• More esoteric: String kernel, chi-square kernel, histogram intersection kernel,…

## multi-class classification

Many SVM packages have built-in multi-class classification
Otherwise, use one vs. all method (train K SVMs, one to distinguish $y=i$ from the rest, for $i=1,2,...,K$), get $\theta^{(1)},\theta^{(2)},...,\theta^{(K)}$. Pick class i with largest $(\theta^{(i)})^Tx$.

## Logistic regression vs. SVMs

1. If n is large relative to m (n=10000, m =10-1000), use logistic regression or SVM without a kernel
2. If n is small, m is intermediate (n=1-1000, m=10-10000), use SVM with Gaussian kernel
3. If n is small, m is large (n=1-1000, m >50000), create/add more features, then use logistic regression or SVM without a kernel

Neural network likely to work well for most of these settings, but may be slower to train.


text:
Browse Questions

# A solution containing 10g/litre of sucrose has an osmotic pressure of 0.66 atm at 273 K. Calculate the value of the constant R.

$0.0827L atm K^{-1}mol^{-1}$


text:
### Denoising and Demosaicking of Color Images

##### Description
 Title: Denoising and Demosaicking of Color Images Authors: Rafi Nazari, Mina Date: 2017 Abstract: Most digital cameras capture images through Color Filter Arrays (CFA), and reconstruct the full color image from the CFA image. Each CFA pixel only captures one primary color component at each pixel location; the other primary components will be estimated using information from neighboring pixels. During the demosaicking algorithm, the unknown color components will be estimated at each pixel location. Most of the demosaicking algorithms use the RGB Bayer CFA pattern with Red, Green and Blue filters. Some other CFAs contain four color filters. The additional filter is a panchromatic/white filter, and it usually receives the full light spectrum. In this research, we studied and compared different four channel CFAs with panchromatic/white filter, and compared them with three channel CFAs. An appropriate demosaicking algorithm has been developed for each CFA. The most well-known three-channel CFA is Bayer. The Fujifilm X-Trans pattern has been studied in this work as another three-channel CFA with a different structure. Three different four-channel CFAs have been discussed in this research: RGBW-Kodak, RGBW-Bayer and RGBW- $5 \times 5$. The structure and the number of filters for each color are different for these CFAs. Since the Least-Square Luma-Chroma Demultiplexing method is a state of the art demosaicking method for the Bayer CFA, we designed the Least-Square method for RGBW CFAs. The effect of noise on different CFA patterns will be discussed for four channel CFAs. The Kodak database has been used to evaluate our non-adaptive and adaptive demosaicking methods as well as the optimized algorithms with the least square method. The captured values of white (panchromatic/clear) filters in RGBW CFAs have been estimated using red, green and blue filter values. Sets of optimized coefficients have been proposed to estimate the white filter values accurately. The results have been validated using the actual white values of a hyperspectral image dataset. A new denoising-demosaicking method for RGBW-Bayer CFA has been presented in this research. The algorithm has been tested on the Kodak dataset using the estimated value of white filters and a hyperspectral image dataset using the actual value of white filters, and the results have been compared. The results in both cases have been compared with the previous works on RGB-Bayer CFA, and it shows that the proposed algorithm using RGBW-Bayer CFA is working better than RGB-Bayer CFA in presence of noise. URL: http://hdl.handle.net/10393/35802http://dx.doi.org/10.20381/ruor-6809 Collection Thèses, 2011 - // Theses, 2011 -