The max-norm minimization in non-synchronous measurements
Liang Yu(1)(4) , Yi Fan(2) , Jerome Antoni(3) ,Haijun Wu(1) , Quentin Leclere(3) , Baihua Yuan(1) , Weikang Jiang(1)(1) Institute of Vibration, Shock and Noise, School of Mechanical Engineering, Shanghai Jiao Tong University, P.R. China(2) Hagong Intelligent Robot Co., Ltd, P.R. China(3) Laboratoire Vibrations Acoustique (LVA), University of Lyon, INSA-Lyon, France(4) Key laboratory of Aerodynamic Noise ControlAbstract
Acoustic imaging technique based on microphone array is limited by the size and density of the array, andthe method of the non-synchronous measurements is a way to beyond these constraints. The core problem
of archiving the non-synchronous measurements of microphone array boils down to a matrix completion of a
block diagonal spectral matrix. In this paper, the max-norm minimization is investigated for the spectral matrix
completion. Second, the rank, nuclear-norm and max-norm have been investigated as complexity measures in
the context of spectral matrix completion, and their performances are compared at different frequencies and low
signal-to-noise ratio.
Keywords: Max-norm Minimization, Low-rank Model, Microphone Array Signal Processing

1INTRODUCTION

Acoustic imaging is an array-based measurement method for sound source location and quantiﬁcation, which
has been widely applied in the underwater detection, medical imaging and so on [1, 2]. Two well-known
acoustic imaging techniques are Beamforming (BF) and Near-ﬁeld Acoustical Holography (NAH). Beamforming
is an acoustic imaging technique for medium to long measurement distance. The resolution of BF is inversely
proportional to the array diameter measured in units of wavelength. The array diameter is required very large
at low frequencies, which usually cannot be satisﬁed. NAH requires short measurement distances, which is lessthan half a wavelength. The number of measurement points is supposed to be very dense at high frequency[4].
A way for achieving a large array and high microphone density is to scan the object of interest by moving
sequentially a prototype array (an arbitrary array), which is referred to as non-synchronous measurements [5].
In comparison to a large array and high microphone density array that can acquire simultaneously all the information of the spectral matrix, in particular all cross-spectra, non-synchronous measurements can only acquirea block diagonal spectral matrix, while the cross-spectra between the non-synchronous measurements remain
unknown due to the missing phase relationships between consecutive positions.
The unknown cross-spectra can be estimated by the low-rank matrix completion (MC) techniques [6]. The
rank minimization and the minimization of its convex relaxation, such as nuclear-norm minimization, are coreprocesses in the MC algorithms. The rank and nuclear-norm are used in the cross-spectral matrix (CSM) completion problem in Ref. [6, 7] with corresponding cyclic projection (CP) algorithm and FISTA algorithm. Itis veriﬁed that the nuclear norm outperforms the rank in the condition of different signal-to-noise ratio (SNR).
Although it is considered that the max-norm performs better than the rank or the nuclear-norm in the theoreticalconditions, there is no analysis of how the max-norm performs in the CSM completion problem. It is notedthat the MC techniques of max-norm in aforementioned investigations cannot be directly used for solving theCSM completion problem. The max norm minimization algorithm for CSM completion problem is supposed tobe introduced.

127

2

ACOUSTICAL SOURCE RECONSTRUCTION FROM NON-SYNCHRONOUS MEASUREMENTS

2.1 Problem statement
The sound pressures are measured by the microphone array, and then the CSM in each measurement can beestimated. These CSMs can be methodically rearranged in the block diagonal positions of an incomplete CSM.
The scheme of the non-synchronous measurement is shown in Fig. 1. When the CSM is completed, the acoustic
image can be easily reconstructed. With the purpose of implementing the non-synchronous measurements, theproblem is formulated as to seek a full CSM from the CSM of data missing.

measuring0collecting signals

completingthe matrix

0
Figure 1. Scheme of non-synchronous measurements: the sound pressure is measured with a moving small
microphone array. The collected signals are formulated as a CSM with data missing. The missing elements inthe CSM are estimated.
2.2 The matrix complexity measures
Matrix complexity was introduced in Ref. [8] to analyze the low-rank matrix completion problem. It is indicatedin Ref. [8] that the complexity can be measured by the rank, nuclear-norm and max-norm. The choice of thecomplexity measure in the matrix completion problem is highly relevant to the performance of the solving
methods. Thus, the properties of each matrix complexity measure (rank, nuclear-norm and max-norm), and therelationships of the complexity measures are supposed to be investigated. For a matrix S ∈ Rm×n , the complexity
measures are deﬁned as below.
1. Rank(S) is the the minimum k such that S = UV∗ , U ∈ Rm×k , V ∈ Rn×k .
min(m,n)2. Nuclear-norm S∗ : S∗ := ∑k=1
σk2 (S), which is the sum of all eigenvalues values: σ12 (S) ≥ σ22 (S) ≥2· · · σmin(m,n) (S). And nuclear-norm can also be equivalently written as:S∗ = inf∑ |σ 2j (S)| : S = ∑ σ 2j (S)u j vTj , u j ∈ Rm , v j ∈ Rn , u j 2 = v j 2 = 1 ,j(1)jwhere the u j and v j denote eigenvectors of the matrix S corresponding to the jth eigenvalue σ 2j .
3. Max-norm Smax is deﬁned as matrix factorization:Smax = min{L2,∞ R2,∞ : S = LR∗ }, L ∈ Rm×k , R ∈Rn×k , where  · 2,∞ denotes the maximum row norm of a matrix: A2,∞ := max j (∑ j A2jk )1/2 and A jk
denotes the element of A jk at jth row kth column.
2.3 Max-norm minimization
The max-norm is an alternative convex relaxation for the rank in the low-complexity matrix completion problem, which is considered to be better than nuclear-norm in theoretical cases [9]. It is deﬁned that the M is the128

number of microphones in the prototype array and P the number of non-synchronous measurements. When the(i)sound pressures p ∈ CM are measured by the microphone array, the CSM Ŝ pp ∈ CM×M of ith measurement can(i)be estimated. The CSMs Ŝ pp , i = 1, ..., P (spectral matrices for short hereafter) in non-synchronous measurements are methodically rearranged in the block diagonal positions of an incomplete CSM Ŝmpp ∈ CMP×MP . The
data missing CSM completion based on max-norm can be formulated as the following constrained optimization
problem:minimize SmaxSsubject to A (S) − Ŝmpp F ≤ εΨSΨ∗ − SF ≤ ε(2)S∗ = S  0,

1. Object function: Smax is the max-norm of S.
2. System equation constraint: measurement data ﬁtting is imposed as a constraint A (S) − Ŝmpp F ≤ ε,where  · F denotes the Frobenius norm: XF = ∑i j X2i j . The difference between A (S) and Ŝmpp inFrobenius norm is less than a given tolerance ε that is composed of estimation and measurement errors.
The sampling operator A is deﬁned formally as follows.
[S]i j i j ∈ Υmm
S pp = A (S) with [S pp ]i j =/ Υ,[S]i j i j ∈where []i j denotes the (i, j) element of a matrix and Υ denotes the positions of ﬁxed block diagonal
entries.
3. Spatial continuity constraint: in order to ensure spatial continuity of the acoustic ﬁeld, the information on
microphone positions must be encoded in the CSM: ΨSΨ∗ − SF ≤ ε, where Ψ = ΦΦ† is a projection
basis (the purpose of this representation is to construct an inner structure of the CSM as a constraint tosolve a matrix completion problem). The Ψ∗ denotes the transpose-conjugate of Ψ, Φ ∈ CMP×Kp andΨ ∈ CMP×MP , where K p is the dimension of basis.
4. Hermitian property constraint: S∗ = S  0, where  denotes positive semi-deﬁnite. The Hermitian property
is an inherent characteristic of the CSMs, as well as the fact that its eigenvalues are non-negative.
The object function, the max-norm of the CSM, can be further rewritten as
Smax = minimize(L,R):LR∗ =Smax{L22,∞ , R22,∞ }.

(3)

The formulation (3) of the max-norm is non-convex due to the constraint on the product LR∗ . The aforementioned problem (2) can be rewritten with the max-norm as a regularization term:
minimizeSA (S) − Ŝmpp F + β Smaxsubject to ΨSΨ∗ − SF ≤ εS∗ = S  0,(4)where β is a positive penalty parameter. Let the object matrix S is factorized
as S = LR∗ . A matrix A Lis deﬁned to the matrix of factors stacked on top of one another A =. Thus, it can be obtained thatR129

A22,∞ = max{L22,∞ , R22,∞ }. Also let f˜(A) denote A (S) − Ŝmpp 2F . The original max-norm minimization
problem can be further written asminimize
Sf˜(A) + λ A2,∞

subject to rank(S) ≤ dΨSΨ∗ − SF ≤ εS∗ = S  0.

(5)

A constraint of rank is added to accelerate convergence in the above max-norm minimization problem (5). Aproximal-point algorithm can be obtained to solve the max-norm minimization problem (3) based on Ref. [3].
2.4 Simulation
In general, the spatial sampling frequency of the microphone array is governed by the Nyquist Shannon sampling theorem, which declares that the working frequency range of the array is determined by its size andthe microphone density [4]. It is considered according to Nyquist Shannon sampling theorem that the working frequency must be lower than 1700 Hz in the simulation, or the measurements are invalidated. The matrix
completion error (MCE) and acoustic reconstruction error (ARE) of the three matrix complexity measures versus
different working frequency are shown in Fig. 2. The CSM completion error (MCE) is calculated as
MCE ={sim}{sim}S pp{com}− S pp{sim}S pp F

F,(6){com}

where S pp is the true (simulated) CSM and S pp
is the completed one. The acoustical reconstruction error(ARE) is calculated as
S{sim} − S{rec} F
(7)
,
ARE =
S{sim} F
where S{rec} is the reconstructed CSM from the completed CSM. Figure. 2 shows that the MCE or ARE of
the three complexity measures are far lower than 1.0 under any working frequency, which indicate that the nonsynchronous measurements make a breakthrough of Nyquist Shannon sampling theorem. The ARE and MCE ofthe max-norm are relatively high at low frequency (< 2100Hz), and those of nuclear-norm are fairly low at anyfrequency. However, at high frequency (> 2100Hz), the MCE and ARE of max-norm are signiﬁcantly lower
than nuclear-norm. In other words, max-norm owns superiority at high frequency in the acoustic reconstruction
problem.
High noise is added here to compare the performance of the three matrix complexity measures. Fig. 3 shows
the MCE and ARE of the three complexity measurements versus different frequency. The MCE of the maxnorm are the highest at low frequency (< 2100Hz), while the MCE of the max-norm equals to the MCE of therank or the nuclear-norm at high frequency (> 2100Hz). The ARE of max-norm is almost the lowest, especiallyat high frequency (> 2100Hz). The robustness of max-norm is better than rank, and nuclear-norm in the caseof noise.
The images of acoustic source reconstruction based on the full CSM and data missing CSMs (completed byrank minimization, nuclear-norm minimization and max-norm minimization) are shown in Fig. 4. Figure. 4
shows that the results of acoustic image reconstruction based on max-norm minimization is signiﬁcantly better
than the reconstruction results of the rank minimization and the nuclear-norm minimization at SNR = 20 dB,
which indicates that the max-norm minimization is far more robust to noise than the rank minimization and thenuclear-norm minimization.

130

100-1

10-2

10-310-110-210-3Rank
Nuclear-Norm
Max-Norm

ARE

MCE

10100Rank
Nuclear-Norm
Max-Norm

10-41010-4-501000

2000

3000

4000

Frequency [Hz]

(a)

5000

6000

7000

10-501000

2000

3000

4000

5000

6000

7000

Frequency [Hz](b)

Figure 2. Reconstruction error versus working frequency without noise: (a) MCE, (b) ARE. Results of rank areshown by red circles; nuclear-norm by green asterisks. max-norm by blue diamonds.

3Conclusion

In summary, the max-norm minimization of the acoustic CSM completion problem is investigated in the nonsynchronous measurements. The rank, nuclear-norm and max-norm are compared in the simulation. The resultsof the simulation show that the reconstruction errors of each complexity measures are determined by workingfrequency. The performance of the max-norm is superior to the rank or the nuclear-norm at high frequency (>2100Hz).

ACKNOWLEDGEMENTS
This work was supported by National Natural Science Foundation of China (Grant No. 11704248) and OpenFund of the Key Laboratory of Aerodynamic Noise Control (ANCL20180302).

131

10010-110-110-210-210-310-3ARE

MCE

10010-4

1010-4

Rank
Nuclear-Norm
Max-Norm-501000

2000

3000

4000

Frequency [Hz](a)

5000

6000

Rank
Nuclear-Norm
Max-Norm

7000

10-501000

2000

3000

4000

5000

6000

7000

Frequency [Hz](b)

Figure 3. Reconstruction error versus working frequency : (a) MCE versus frequency with SNR= 20 dB, (b)ARE versus frequency with SNR= 20 dB. The results of rank are shown by red circles; nuclear-norm by green
asterisks; max-norm by blue diamonds.

REFERENCES[1] Kompis M, Pasterkamp H, Wodicka G R. Acoustic imaging of the human chest[J]. Chest, 2001, 120(4):1309-1321.
[2] Sutton J L. Underwater acoustic imaging[J]. Proceedings of the IEEE, 1979, 67(4): 554-566.
[3] Rockafellar R T. Monotone operators and the proximal point algorithm[J]. SIAM journal on control andoptimization, 1976, 14(5): 877-898.
[4] Hald J. Combined NAH and beamforming using the same array[J]. Technical, 2005: 11.
[5] Yu L. Acoustical source reconstruction from non-synchronous sequential measurements[D]. INSA de Lyon,
2015.
[6] Yu L, Antoni J, Leclere Q. Spectral matrix completion by Cyclic Projection and application to sound sourcereconstruction from non-synchronous measurements[J]. Journal of Sound and Vibration, 2016, 372: 31-49.
[7] Yu L, Antoni J, Leclere Q, et al. Acoustical source reconstruction from non-synchronous sequential measurements by Fast Iterative Shrinkage Thresholding Algorithm[J]. Journal of Sound and Vibration, 2017,408: 351-367.
[8] Srebro N, Shraibman A. Rank, trace-norm and max-norm[C]//International Conference on Computational
Learning Theory. Springer, Berlin, Heidelberg, 2005: 545-560.
[9] Cai T T, Zhou W X. Matrix completion via max-norm constrained optimization[J]. Electronic Journal ofStatistics, 2016, 10(1): 1493-1525.

132

0.5

0.5

0-2-2-40-0.5
-0.5

-4

0

0

0.5

-6-6-8-8-10

-0.5
-0.5

0(a)

(b)

0.5

00.5

-2-2-4-4

0-0.5
-0.5

0.5

000.5

(c)

-6-6-8-8-0.5
-0.5

00.5

-10(d)

Figure 4. acoustic source reconstruction based on (a) full spectral matrix, (b) data missing spectral matrix
completed by rank minimization, (c)data missing spectral matrix completed by nuclear-norm minimization and(d) data missing spectral matrix completed by max-norm minimization. The f = 3000 Hz and SNR= 20 dB.

133