Average Case Analysis of Compressive Multichannel Frequency Estimation Using Atomic Norm Minimization
1
Citation
16
Reference
10
Related Paper
Citation Trend
Abstract:
Compressive multichannel frequency estimation refers to the process of retrieving the frequency profile shared by multiple signals from their compressive samples. A recent approach to this problem relies on atomic norm minimization which exploits joint sparsity among the channels, is solved using convex optimization, and has strong theoretical guarantees. We provide in this paper an average-case analysis for atomic norm minimization by assuming proper randomness on the amplitudes of the frequencies. We show that the sample size per channel required for exact frequency estimation from noiseless samples decreases as the number of channels increases and is on the order of K log K (1+ 1/L log N), where K is the number of frequencies, L is the number of channels, and N is a fixed parameter proportional to the sampling window size and inversely proportional to the desired resolution.Keywords:
Minification
This work starts from definition of randomness, the results of algorithmic randomness are analyzed from the perspective of application. Then, the source and nature of randomness is explored, and the relationship between infinity and randomness is found. The properties of randomness are summarized from the perspective of interaction between systems, that is, the set composed of sequences generated by randomness has the property of asymptotic completeness. Finally, the importance of randomness in AI research is emphasized.
Completeness (order theory)
Infinity
Randomness tests
Cite
Citations (0)
Abstract We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property (N) if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1({\mathcal {O}})$ -randomness, and if and only if it reflects ${\mathcal {O}}$ -Kurtz randomness, but reflecting Martin–Löf randomness or weak-2-randomness does not suffice. Here a function f is said to reflect a randomness notion R if whenever $f(x)$ is R -random, then x is R -random as well. If additionally f is known to have bounded variation, then we show f has Luzin’s (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset '$ -Kurtz randomness. This links classical real analysis with algorithmic randomness.
Cite
Citations (1)
I investigate the trade-off between regularity and randomness in Bridget Riley's early Op art, focusing on White Discs 2 (1964) and Fragment 6/9 (1965). I build on this to investigate the trade-off more generally. I analyse these two works and undertake three experimental investigations based on my observations. I first consider different types of randomness and the effect they have on the generated artwork. I then look at whether the introduction of randomness can be left to the computer or needs the artist's direction. For best aesthetic effect, there is some evidence that the choices made are not truly random. Finally, I consider how much randomness needs to be added to a regular pattern in order to produce a work that balances regularity and randomness in an aesthetically pleasing way. There is evidence that around two-thirds of the pattern needs to be retained.
Cite
Citations (9)
We show that a computable function $f:\mathbb R\rightarrow\mathbb R$ has Luzin's property (N) if and only if it reflects $\Pi^1_1$-randomnes, if and only if it reflects $\Delta^1_1(\mathcal O)$-randomness, and if and only if it reflects $\mathcal O$-Kurtz randomness, but reflecting Martin-L\"of randomness or weak-2-randomness does not suffice. Here a function $f$ is said to reflect a randomness notion $R$ if whenever $f(x)$ is $R$-random, then $x$ is $R$-random as well. If additionally $f$ is known to have bounded variation, then we show $f$ has Luzin's (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset'$-Kurtz randomness. This links classical real analysis with algorithmic randomness.
Cite
Citations (0)
Abstract In a number of studies, tendencies toward nonrepetition in judgments of randomness of visually presented sequences of events have been attributed to a biased concept of randomness. The present study proposed that such bias is due to “bottom-up” visual processes rather than a concept of randomness. Experiment 1 showed that judgments of randomness were less biased when repetitions were made less conspicuous by increasing the distance between adjacent items. Experiment 2 produced comparable results for increasing dissimilarity of categorically identical items. A third experiment showed that the bias in the judgment task was not related to a more direct measure of knowledge of random processes, the assignment of probabilities of repetition to imagined random sequences. The results supported the view that judgments of randomness are determined to a high degree by the conspicuousness of repetitions and are independent of the concept of randomness.
Repetition (rhetorical device)
Random sequence
Degree (music)
Cite
Citations (10)
Randomness tests
Cite
Citations (6)
Recent work in compressed sensing theory shows that m×n independent and identically distributed sensing matrices whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if m≪n. In particular, it is well understood that the L1 minimization algorithm is able to recover sparse signals from incomplete measurements. In this paper, we propose a novel sparse signal reconstruction method that is based on the reweighted L1 minimization via support recovery.
Minification
Signal Recovery
Signal reconstruction
SIGNAL (programming language)
Cite
Citations (3)
Abstract This paper is a concept paper, which discusses the definition of randomness, and the sources of randomness in the physical system (the Universe) as well as in the formal mathematical system. I discuss how randomness, through chaos, the second law, the quantum mechanical character of small scales, and stochasticity is an intrinsic property of nature. I then move to our formal mathematical system and show that even in this formal system we cannot do away with randomness and that the randomness in the physical world is consistent with the origins of randomness suggested from the study of mathematical systems. Rules and randomness are blended together and their interaction is shaping all observed forms and structures.
Formal description
Randomness tests
Cite
Citations (1)
This work starts from definition of randomness, the results of algorithmic randomness are analyzed from the perspective of application. Then, the source and nature of randomness is explored, and the relationship between infinity and randomness is found. The properties of randomness are summarized from the perspective of interaction between systems, that is, the set composed of sequences generated by randomness has the property of asymptotic completeness. Finally, the importance of randomness in AI research is emphasized.
Completeness (order theory)
Infinity
Randomness tests
Cite
Citations (0)
Abstract We study the strengths of various notions of higher randomness: (i) strong ${\rm{\Pi }}_1^1$ randomness is separated from ${\rm{\Pi }}_1^1$ randomness; (ii) the hyperdegrees of ${\rm{\Pi }}_1^1$ random reals are closed downwards (except for the trivial degree); (iii) the reals z in $NC{R_{{\rm{\Pi }}_1^1}}$ are precisely those satisfying $z \in {L_{\omega _1^z}}$ and (iv) lowness for ${\rm{\Delta }}_1^1$ randomness is strictly weaker than that for ${\rm{\Pi }}_1^1$ randomness.
Degree (music)
Cite
Citations (13)